Naruto: A New Destiny
by Advent of Shadows
Summary: After a lapse in control at the Valley of the End, Naruto's status as a Leaf shinobi is revoked. Feeling betrayed by one of his precious people, Naruto leaves the village and embarks upon a path that will shake the world to its core. Naruto/Tayuya
1. Control

Summary: After a lapse in control at the Valley of the End, Naruto's status as a Leaf shinobi is revoked. Feeling betrayed by one of his precious people, Naruto leaves the village and embarks upon a path that will shake the world to its core. NaruTayu

Warnings: This work of fanfiction is rated M for language and violence.

* * *

Disclaimer: I do not own Naruto.

* * *

**New Destiny Arc**

**1. Control**

Kakashi Hatake took a deep breath as he followed after Pakkun through the dense forests of the Land of Fire. They were still tracking down Naruto Uzumaki, who was currently trying to bring Sasuke Uchiha back to the Village Hidden in the Leaves.

_I hope I'm not too late._ It was a little funny, in a way, that he was actually worried about being on time for the first time since he received his Sharingan eye. He could not find it in him to so much as think about laughing at that moment though.

Relief filled Kakashi as he finally reached the Valley of the End, but his relief did not last long. The only thing that he saw there was Naruto Uzumaki. The blond was standing on the water below the giant statues of Madara Uchiha and Hashirama Senju, but that was not the alarming thing.

The alarming thing was that Naruto was standing like an Inuzuka would in combat, and red chakra was covering his body. The chakra seemed to form a cloak that resembled a fox with a single tail. His knowledge of jinchuriki in general told him that Naruto had drawn out quite a bit of the fox's chakra.

"Pakkun, do you remember Sasuke's scent?" Kakashi asked quietly.

"Yeah, I do," the dog said, clearly thinking back to when he had to track down Sasuke when the Hidden Sand Village and the Hidden Sound Village joined forces to invade the Hidden Leaf Village. "His scent leads away from here, and I can't smell much blood at all. I'd bet my paw that he's alive."

Kakashi sighed in relief before he looked at Naruto again. "In that case, I'm going to try to calm Naruto down."

With those words spoken, Kakashi disappeared in a flicker of movement and reappeared about twenty yards in front of Naruto.

The instant that he reappeared, Naruto lunged forward to attack him, forcing Kakashi to jump out of the way.

_What in the hell's going on? Can't he recognize me?_

He continued to frown as Naruto attacked him again and again. His suspicions seemed to be confirmed, and that was not something that he liked in the least.

_It looks like I only have one option._ He quickly uncovered his Sharingan eye at that point.

It only took a few moments for Kakashi to make eye contact with Naruto and to cast a genjutsu on him. Relief filled him as Naruto fell asleep and the chakra cloak faded. With his Sharingan's job done, he covered it up.

_I guess Sasuke's going to have to wait. Something's clearly wrong with Naruto. Maybe Lady Hokage or Master Jiraiya can figure it out._

With that in mind, he began to race back to the Hidden Leaf Village with the unconscious Naruto in his arms.

* * *

"Lady Hokage, I need your help."

Tsunade's eyes went from her desk to Kakashi Hatake, who was holding an unconscious Naruto in his arms. She immediately rose from her desk and opened a nearby closet door. Inside the closet was actually a mini-bedroom with a cot.

"Set him down in here, and I'll work on healing him," she said, seeing the injuries all over his body. It looked as though he had been through hell and back.

"Yes, Lady Hokage," Kakashi said as he did as instructed. He then backed off so Tsunade could enter the small room and work on healing him.

A few seconds later, she looked at the Copy Ninja strangely. "Why is he in a genjutsu-induced sleep?"

Kakashi sighed at that question. "Naruto drew out too much on the fox's chakra during his fight with Sasuke. He entered a stage one tailed beast transformation. His chakra cloak had a single tail on it when I got there, so I prepared for anything. He immediately began attacking me, so I had to use my Sharingan to incapacitate him."

That earned a frown with Tsunade. "He attacked you, and he was only using a stage one, one-tailed transformation?" she asked, clearly surprised. "And what happened to Sasuke?"

"Knowing Sasuke, he probably incapacitated Naruto for a few moments with his Sharingan before he ran off. Pakkun did confirm that Sasuke's scent went beyond the Valley of the End, and he did not smell _that_ much blood in the air," Kakashi said. He was glad that Tsunade relaxed at that news. "And yes, Naruto did attack me in that state."

Worry was clear on Tsunade's face as she continued to work on Naruto. "Did sensei brief you on the Nine-Tailed Demon Fox's history?"

"If you're referring to its history with the village and its past two jinchuriki, then the answer is yes," Kakashi answered with a frown. "Now that I think about it, Mito Uzumaki was your grandmother, wasn't she?"

Tsunade nodded her head with a wistful smile. "Grandma was a remarkable person. After Mom and Dad died, she raised me and Nawaki. But more than that, she was an incredible jinchuriki. I once saw her enter a second stage transformation with four tails, and she maintained complete control. The trick, she said, was that you had to possess complete control of your emotions not to succumb to the fox's will in order to control the transformation." She looked at Naruto with a frown at that. "It took more and more control in order to control more of the fox's chakra. However, the one-tailed transformation that Naruto went through should have been easy to remain in control of."

Kakashi frowned at hearing that. If anyone knew about the difficulty of controlling the fox, it would have had to be Tsunade, who had spent time around all three jinchuriki of the Nine-Tailed Demon Fox. The lack of control that Naruto possessed worried him.

"I'm going to have to take drastic measures," Tsunade said with a sigh. "Until he learns sufficient control over his own emotions, he cannot be allowed to leave the village, or even be put into a situation where he could draw on the fox's chakra."

Kakashi's frown deepened at that. "What do you mean, Lady Hokage?"

"I'll tell you later. If you would, go to the hospital and find Shikaku Nara. He should be there with his son. Tell him that I need him to call a meeting," Tsunade said as she began to look over Naruto again. His injuries had healed enough before he showed up that his condition had not been life threatening, but he still had a number of cuts and scrapes on him.

If not for the fact that she was still worn out from healing Choji Akimichi, she would have finished healing his minor injuries. However, healing the boy had taken a great deal out of her, especially after she had healed Rock Lee only a few days ago.

_Naruto, I hope you can forgive me for what I'm about to do._

* * *

About an hour after Kakashi Hatake returned to the Village Hidden in the Leaves, Tsunade was seated in one of her various meeting rooms with Shikaku Nara, Koharu Utatane, and Homura Mitokado.

"May I ask why you've asked us to meet so late?" Homura asked politely. Being in his late sixties with what basically amounted to a desk job, he was not used to being called a way to business after the sun was down.

"It seems that we have a problem," Tsunade said calmly. "Naruto Uzumaki had a lapse in control during the mission to retrieve Sasuke Uchiha. Kakashi Hatake came upon him, only to discover that he had drawn upon enough of the fox's chakra to enter a basic one-tailed transformation. He did not only draw upon enough of its chakra to enter that transformation, however. He was unable to separate its chakra from its will, and it gained temporary control of him, causing him to attack Kakashi."

The advisors and the Jonin Commander looked worried at that news. It was always grim to hear that a jinchuriki lost control, especially after only using such a small sliver of their full power.

"Kakashi restrained him with a Sharingan-induced genjutsu, and I personally looked him over. The chakra that flowed through his chakra system was entirely his own, so he's in control again. However, I'm still worried about him," Tsunade said with a heavy sigh. "As you all know, my grandmother was the first jinchuriki of the Nine-Tailed Demon Fox. She spoke of her powers to me often in my youth, and she made it clear to me that it did not take much control in order to resist the fox's will at the one-tailed state. Given that he could not resist the fox's will, despite that, and he lacks the ability to suppress the fox's will through any special means, I've had to come to a difficult decision. Naruto Uzumaki cease to be a shinobi of this village until he displays the necessary control of his emotions to allow him to resist the fox's influence. Furthermore, he is to be restricted from leaving the village until that time."

"I agree with your decision," Homura said immediately. "However, perhaps he should be given to Danzo in addition to that. If anyone can help him resist the fox and its influence, it would be him."

Koharu nodded her head in agreement at that.

"I disagree with the advisors on this one," Shikaku said, earning scowls from the elder shinobi. "Danzo Shimura is a warhawk. While he may be able to free young Naruto from the fox's control, he could only manage it by stripping the boy's emotions away. I've seen what he does to those he trains. He doesn't teach emotional control. He flat out removes the emotions and turns his trainees into living weapons. That's the last thing we need for Naruto."

The advisors looked furious at Shikaku's words, but they brought a smile to Tsunade's face. "I agree with Shikaku on this. Instead, we will make arrangements with Inoichi Yamanaka so that he may undergo therapy. The issues he's having with control will go away once he comes to terms with what he's feeling."

It was clear that the advisors disagree with her, but they chose not to say anything in the end.

_Now, I just need to tell him about it._She expected that telling him about her decision would be the hardest part about the whole ordeal.

* * *

Naruto groaned as he began to wake up.

Immediately, he remembered his fight with Sasuke at the Valley of the End.

He inwardly shuddered as he remembered drawing upon a large amount of the fox's chakra as Sasuke transformed into something different with the help of his curse mark.

The fight had been difficult when he fought Sasuke in their transformed states. In fact, the only reason that he had won the fight was because Sasuke had taunted him relentlessly, and he had let bloodlust overcome him.

He flinched at the thought that he won the fight. He knew that he did not truly win it. After all, Sasuke had pulled a fast one on him at the end of the fight. After Naruto had knocked him into one of the statues that sat at the waterfall, a cloud of dust came up and Sasuke emerged in his regular form.

Well, he had thought it was Sasuke, at least. Apparently, Sasuke had copied the Shadow Clone Jutsu from him during the match and sent out a shadow clone to fight him while the real one fled.

After he realized the deception, he had blacked out, anger consuming him.

Opening his eyes, he saw Tsunade next to him. He slowly sat up and looked at her.

"Are you feeling alright?" she asked.

"Never felt better," he said, though his body screamed in protest. "Where am I?"

"We're in a room that's connected to my office," Tsunade said quietly. "I'm sorry, Naruto. The mission was a failure."

"I know," Naruto said just as quietly. Turmoil raged behind his eyes as he said it. "If I had stayed in control, he wouldn't have been able to trick me like that."

"How did he get by you?" she asked curiously.

"He copied my Shadow Clone Jutsu and ran off when I was distracted," Naruto said in annoyance. It truly irked him how Sasuke stole his jutsu and used it against him.

"Do you remember anything beyond that?" she asked, worry in her voice.

"No," he said with a frown. "Should I?"

"Kakashi went to get both of you back, but you attacked him when he showed up. The fox was in control, apparently," she said with a heavy sigh.

Panic filled Naruto at hearing that. He could not believe that he attacked Kakashi like that. "Is he okay?"

Tsunade let out a small, hollow laugh. "You're good, but he's a jonin. He came out of it without a scratch."

Naruto let out a sigh of relief at that news.

"But, I have bad news for you," Tsunade said, earning a frown from the blond. "The Nine-Tailed Demon Fox's power comes in two parts: its chakra and its will. You cannot draw one without the other. If you are able to retain control over your emotions, you can draw out both and separate them so that the fox's will won't affect you. However, you were unable to control your emotions, and the fox gained control over you as a result."

"Why are you telling me how it happened?" Naruto asked with a frown. The long explanation of what happened did not really matter to him, after all.

"Naruto, it's important. Until you gain the control over your emotions necessary to resist the fox's will while at least drawing upon a small amount of its chakra, I have no choice but to remove you from the shinobi ranks of this village."

Rage surged through Naruto at that. "You can't do that! You can't just kick me out after everything I've done for the village!"

"Yes, I can," Tsunade said with a sigh. "Naruto, you're only proving that you can't control your emotions."

Naruto quickly stood up, surprising Tsunade. "You can't be serious! You just can't!"

"I am," she said with a frown.

"If you do this… I'm going to leave," Naruto said, anger and pain clear in his eyes. He could not believe that one of his precious people was doing something like that to him.

"You're restricted to the village," Tsunade said quietly. "You may not leave it for any reason."

"I can't believe you're doing this to the one that brought you back to this village," he said, his hand moving to the back of his head. He untied his forehead protector and handed it to her. "I should never have brought you back."

Pain was clear on Tsunade's face as walked past her and left the building.

* * *

Many miles from the Hidden Leaf Village, there was an entire area of forest that had been cut down. No tree in the area remained intact, and the logs that had been left as a result were never more than fifteen feet long.

Pinned between two logs, there was a redheaded girl with brown eyes. She was clad in the attire of a Sound shinobi. She was not just _any_ Sound shinobi though. She was the only kunoichi of the Sound Four.

Her name was Tayuya of the North Gate, and she appeared to be dead.

But in reality, that was just a ruse.

Her eyes snapped opened to the dark of the night. Pain filled her chest, alerting her to the log that was on top of her. It was heavy, and it made it rather difficult for her to breath. Luckily, she had been in her second state form when it landed on her, so it had not broken any bones. Still, she would have been in a bind if she had been breathing at her normal rate for the past six or so hours that the log was on top of her. That was one reason she cast a genjutsu upon herself to induce a false death state. It had slowed down her heart rate and breathing rate, which allowed her to deal with the log on top of her almost comfortably as her chakra recovered.

_I needed that little rest. It feels like I didn't break anything, so I should be able to move around fine. First, I need to get this fucking thing off of me though._

She immediately tried to go straight into her second state form, but she felt incredible pain. In the end, she had to simple use the curse mark's initial form.

_Fuck! I used too much of the curse mark's power when I was fighting that damned rat and that blonde bitch earlier. This form isn't even going to last very long. I better work fast before I revert back to normal._

She quickly slid her hands between the gaps of the log above her and the one below her. Using all of her strength, she tossed it straight into the air. It only went about five feet in the air, but that was all she needed. Using her last remaining moments in her current form, she rolled out of the way and jumped away from the falling log.

She landed about ten yards away and collapsed to her knees in her basic form, her eyes focused on the log that she had thrown as it came crashing down.

_I need to rest. And then, I'll see if there's any sign of fat ass and the others._

Part of her hoped that they were dead already. After all, it would be better if the entire Sound Four was presumed dead. She already knew that she would be killed if she returned to Orochimaru. She had failed to bring Sasuke Uchiha to the base, after all.

* * *

Back in the Hidden Leaf Village, Kakashi appeared in front of Naruto's apartment door with a panicked look on his face. He had just heard about Naruto's removal from the ranks of shinobi thanks to Shizune. It was close to midnight already, but he knew that he had to get to Naruto quickly.

Kakashi was determined to make sure that Naruto did not think he was upset with him or anything, after all.

He opened the front door of Naruto's apartment, frowning when he saw that it was not even locked.

His eyes moved around the dark room as he entered the apartment.

Kakashi made his way through the apartment, checking every room. It appeared that Naruto was not home.

He was about to leave the apartment when he saw something next to Naruto's calendar in his kitchen. It was a note with a kunai embedding it to the wall.

It read:

_I never go back on my word. I may not be one of your ninja anymore, but that's still my ninja way._

_-Naruto Uzumaki_

Kakashi's eyes widened, remembering what Shizune had said about Naruto's words to Tsunade.

_Damn it! He's already left the village._

With all the speed he could muster, Kakashi removed the note from the wall and headed to inform Tsunade of what he had discovered.

As everyone would soon discover, tracking Naruto was not an easy matter. After all, the blond was proficient in the Shadow Clone Jutsu and could create a hundred clones, which could make it difficult for any ninja dog or sensor to figure out the actual path that was taken.

* * *

Author's Note: Thanks for reading the first chapter of my new fic.

In this fic, Naruto and Tayuya will both be freelance shinobi, doing missions throughout the Elemental Nations and becoming both famous and infamous.

This fanfic is the spiritual successor to Betrayal, which will soon be removed (and possibly added to Advent of Shadows' Archive). The two are more different than similar, so this is in no way a rewrite.


	2. A Hero's Return

Author's Note: I noticed that several people referred to Naruto as a missing-nin in their reviews. Because he was actually taken out of the ninja ranks by the Hokage, he's simply a citizen of the Hidden Leaf Village. They can't mark him as a missing-nin, but that doesn't mean that they're not hunting him, though. The Nine-Tails is essentially the village's property, or that's how they look at it at least.

Oh, and I wanted to discuss the poll I had up last chapter right quick. The chapter was about what Naruto would do with Zabuza's sword. It seems that quite a few people failed to understand that Naruto would not wield the sword in any of the options. The "momento" option is just that. He'd keep Zabuza's sword on his wall, or something like that. It's not a practical weapon for him to use.

In the end, I've made my own decision regarding the sword that I'll reveal later.

Now, on to Chapter 2: A Hero's Return

* * *

Disclaimer: I do not own Naruto.

* * *

**New Destiny Arc**

**2. A Hero's Return**

"Lady Hokage, we're back," Kakashi Hatake said as he entered the Hokage's office alongside Tsume Inuzuka.

"You couldn't find him, could you?" Tsunade asked, seeing the grim look in his visible eye.

"It would appear that Naruto created roughly ninety nine false trails during his escape," Kakashi said, surprising her. "His Multi Shadow Clone Jutsu is very useful."

"Surely you can find the real one," Tsunade countered. "You have the entire Inuzuka clan and every ninja dog that the village possesses searching for him."

"Normally, I'd agree with you," Kakashi said with a sigh. "However, it started raining this morning. As a result, some of the trails to the south of the village have been completely wiped away. If the real one went south, we won't be able to find him."

"This is all my fault," Tsunade said with a heavy sigh. "I should have had a squad of ANBU Black Ops keep an eye on him. I didn't think he'd actually leave though."

"There's nothing that can be done about the past, Lady Tsunade," Tsume said with a frown. "That said, I can't blame the kid for running away."

That earned surprised looks from Tsunade and Kakashi.

"Think about it. A couple months ago, the Third Hokage died in combat. Naruto looked up to him like a grandpa. Then, his teammate defects from the village and tries to kill him in the process, from what Kakashi has told me. Next, he loses his position as a genin after all the effort he went through to become a ninja, not to mention the things he's done in the past few months. Finally, he's told that he's basically a prisoner. I'd have been surprised if he didn't lose it and run off, especially since he apparently doesn't have much control over his emotions."

Tsunade and Kakashi both frowned at that analysis. Looking at it like that, it was pretty clear that Naruto had done exactly what they should have predicted that he would do.

"You two can go and get some rest," Tsunade said with a heavy sigh. "When you're rested, return so you can go out and search again. We can't let Naruto roam free."

"Yes Lady Hokage," Kakashi and Tsume said in unison.

* * *

Tayuya sighed for what had to be the millionth time since she woke up from her genjutsu-induced fake death state.

She was sitting in a cave in the Land of Fire without any kind of weapon on her, and it seemed that hundreds of Leaf ninja were roaming the land, looking for something... or someone.

Fortunately, she had discovered a very important bit of news during the night before all of the Leaf ninja showed up. Jirobo, Kidomaru, Sakon, and Kimimaro were all dead. She had found all of their bodies, and it left her feeling a bit hollow.

She was the last living member of the Sound Five.

With the death of the others, it was incredibly likely that she was presumed dead. After all, two of her four dead teammates were stronger than her. Anyone that could easily kill Kimimaro had to have been strong enough to kill her.

She snorted at the thought of Kimimaro's death. His opponent had not doubt been strong, but she could tell that it had not been an easy fight for either of them. The forest of bone stood as a testament to that fact.

Tayuya could honestly say that she was happier about Kimimaro's death than any of the other members of the Sound Five. She had hated him the most.

Rising to her feet, she walked to the opening of the cave and looked around. She had absolutely no idea where she could go from there. She needed to stay under the radar and get out of the Land of Fire, but that was a rather vague direction.

Looking down at her clothes, she sighed. She would need a new change of clothes as soon as she could get them. The garbs that Orochimaru gave them to wear were not entirely inconspicuous.

Closing her eyes, she imagined a map of the Elemental Nations. Thanks to her training, she had memorized every detail of the map.

She immediately ruled out the Land of Sound, the Land of Fire, the Land of Lightning, the Land of Water, the Land of Wind, and the Land of Earth as places she could go. The Land of Rivers, the Land of Rain, the Land of the Waterfall, and the Land of Grass were eliminated as well. All of those were countries Orochimaru had bases in, after all.

The only countries that were left were the Land of Frost, the Land of Hot Water, the Land of Stone, and the Land of Waves. Of those, the Land of Hot Water and the Land of Waves were the only two countries that lacked shinobi villages. Because the former's hidden village-turned tourist resort, it was also a bad choice. If she was found there by anyone that had seen her before, even if they were just on vacation, she would have to go on the run.

_I guess I'm going to the Land of Waves then. It's just south of the Land of Fire, so I should be able to get there without too much difficulty, but I'll have to travel at night until these Leaf ninja stop searching for whatever it is they're searching for. I might have to wait to find some new clothes until I get there, so I'll just have to be creative until then._

Shaking her head, she walked back into her cave and removed the purple belt that Orochimaru's minions wore. Tossing it to the side, she gripped her tunic below her waist. She carefully tore the bottom of it, leaving a ragged hem about an inch below her waist. It removed the corrupt yin-yang symbol from the garb though, which made it more difficult to recognize that she worked for Orochimaru.

Once that was done, she sat down and waited.

* * *

Naruto Uzumaki took a deep breath as he looked at the sight before him. A massive bridge sat before him. It was truly a work of art compared to regular bridges, but that was not what had his attention.

At the start of the bridge, there was a small canopy made of wood and stone with the words _The Great Naruto Bridge_ towards the top.

_Did they name the bridge after me?_ The thought had him puzzled. He had expected that he would be welcomed in the Land of Waves because of his mission there at the start of his ninja career, but he had not expected anything so… monumental.

He walked across the bridge, thinking about its name and the last time he had been there.

By the time he began to take note of his surroundings, he had reached the end of the bridge.

As he walked through the canopy on that side of the bridge, he heard a gasp.

Looking around, he saw an older man that looked like he was looking at a ghost.

"You're the Hero of Wave!" he exclaimed, surprising Naruto. "You are Naruto Uzumaki, aren't you?"

"I am," Naruto said with confusion clear in his eyes. "Did you call me _the Hero of Wave_?"

The old man nodded his head vigorously. "You saved us all from Gato… and ourselves. You're a hero to everyone here."

"I'm not a hero," Naruto said, shaking his head. "All I did was show Inari that he didn't have to give up."

"Heroes… true heroes… inspire people. That's how it's always been, and that's what you did," he countered.

Naruto sighed, seeing that he would not win that argument. "Does Tazuna still live where he did when the bridge was being built?"

"Yeah, he's fond of his old house. He could have had any house of his choosing after the bridge was built, but he's refused to move," the old man said with a chuckle.

"Thanks," Naruto said as he walked away, headed to Tazuna's house.

_How is it that everyone sees me as a hero where I didn't really do anything, but no one saw me as a hero in the place where I did? It just doesn't make any sense._

He could not figure it out. He had saved the Hidden Leaf Village by being the child that the Nine-Tailed Demon Fox was sealed away in nearly thirteen years earlier, he had saved the village from at least partial destruction when the hidden villages of Sand and Sound invaded by fighting and defeating Gaara, and he had saved the village again by convincing Tsunade to return as the Fifth Hokage.

All he did in the Land of Waves, however, was inspire a single boy to fight back.

_Could it just be the fox that makes the difference? I'm seen as a hero in the place that doesn't know about the fox, but no one views me as a hero in the place that does know._

He shook his head as he continued on his way.

* * *

"Hello," Naruto said with a nervous wave.

"Naruto!" Tsunami said as she hugged Naruto through the open doorway. "This is an unexpected surprise. Come on in."

Naruto smiled as he walked by her.

He fell to the ground a few moments after he entered the house as Inari tackled him in a hug.

"I'm glad to see you too," he said with a small laugh. "I'd appreciate it if you got off though. I'm still a bit sore." Saying that without a hint of the pain he felt was a feat in itself. He had not rested for more than three hours since he fought Sasuke at the Valley of the End, so he was thoroughly exhausted. Naturally, his muscles were sore too. Sore muscles did not heal like injuries did for him, after all.

"This is an unexpected surprise," Tazuna said as he entered the room with a smile. "What brings you here, Naruto?"

Naruto sat up as Inari got off of him and looked at Tazuna. "Things are a bit complicated," he said with a frown. "Some things happened, and my team split up. Kakashi-sensei and Sakura are all that's left."

"What do you mean?" Tazuna asked with a frown.

"Sasuke turned his back on the village in order to try to get more power from a rogue ninja," Naruto said. The civilians in the room grimaced at hearing that. "And I basically went berserk after I failed to bring him back, so they took my forehead protector away."

"I'm sorry," Tsunami said with an apologetic look on her face.

"I can understand why you wouldn't want to stay there after that," Tazuna said with a frown. "I wasn't even aware that something like that could happen."

_Neither did I._

"You're welcome to stay here as long as you'd like," Tsunami suddenly said. "You could probably get the deed to any house in town just by asking for it, to be honest. I doubt you'd want to exploit your status here though."

"Thank you. I'd be happy to stay, and no, I won't do anything like that," Naruto said, shaking his head. "I'm going to need another favor from everyone though. For reasons that I'd prefer not to explain, the Hidden Leaf Village is looking for me. They didn't want me to leave, so they'll probably send shinobi to try to bring me back. I'd appreciate it if no one revealed where I am to the Leaf ninja."

"It will cost them our alliance if they try to take you, so long as you're here," Tazuna said firmly. "No one will let them take the Hero of Wave without consequences."

"I doubt they'd care about the alliance," Naruto said sadly. "They _really_ didn't want me to leave. They'd probably be willing to give up a couple allies to get me back."

"Then you'll just have to make sure they don't get you," Tsunami said with a kind smile that was infectious.

"I'll have to do that," Naruto agreed.

"Well, dinner will be in a couple hours. You look tired, so why don't you get some rest for now?" Tsunami asked. "You can take the spare bedroom. It's the same room you slept in last time."

"Thanks," he said as he stood up, yawning. "Thanks for everything.

With that, he walked towards the bedroom.

* * *

Gathered around a dark cave, there were seven hologram-like images of cloaked figures.

"Another meeting so soon? Has something happened?" Sasori of the Red Sand, the greatest S-rank rogue ninja of the Hidden Sand Village, asked as he looked amongst his peers.

"Something had to have happened," Kisame Hoshigaki, one of the Hidden Mist Village's most infamous rogue ninja, said with a grin. "This is our second meeting in a week. We went a couple years without one, and then we have this."

"What has happened?" Itachi Uchiha, the infamous kin slayer of the Hidden Leaf Village's Uchiha clan, asked.

Their leader cleared his throat, ensuring that he had everyone's attention. "It would seem that the jinchuriki of the Nine-Tailed Demon Fox has been kicked out of the shinobi ranks of the Hidden Leaf Village because of a lack of control. Furthermore, he has left the village without their approval. As such, he is no longer under close supervision and he is on the run."

"Should we go after him?" Kisame asked.

"No," their leader said calmly. "Zetsu will monitor him. As it is, the Nine-Tails must be sealed last. Until we have the other eight tailed beasts, we will simply observe him. Keeping him restrained at all times until we are ready to capture him would not be in our best interests."

"Very well then," Itachi said with a nod of his head. "Will that be all?"

"There are only a few matters left to discuss," their leader said as he looked at his subordinates. "Kakuzu, I am working on finding you a new partner. Until I can find one that you cannot kill, you will do your business solo."

Kakuzu, arguably one of the eldest shinobi in the world and a rogue ninja of the Hidden Waterfall Village, simple shrugged his shoulder.

"And Sasori, we are coming close to finding a new partner for you. Naturally, we can't outright replace Orochimaru. He still has his ring, so we're simply looking to recruit a new member. Once we are able to find a suitable candidate, I'll alert you," their leader added. "That will be all for now."

With that, Akatsuki's meeting came to an end.

* * *

Author's Note: I seem to have tons of inspiration for this fic right now, so I expect I'll focus on it instead of Secrets for a little while.

I will say that it's a good idea to check my profile often. I put up new polls about as often as I post chapters.

Thanks for reading and reviewing.

Next chapter, you'll get to see the reactions of Iruka, the Konohamaru Corps, Sakura, Team 8, Team 10, Team Guy, and a few others at learning of Naruto's situation. Keep in mind that they've kept Naruto's disappearance a secret. The only people know know are the Advisors, Tsunade, the Inuzuka clan (minus the academy students and genin of the clan), Kakashi, and Shikaku.

That's not all I'll show either, but I shouldn't reveal too much. I will say that Tayuya's arrival in the Land of Waves will happen in a couple chapters though.


	3. The Truth Revealed

Disclaimer: I do not own Naruto.

* * *

**New Destiny Arc**

**3. The Truth Revealed**

"It looks like you're all here now," Tsunade said as she looked at Kakashi Hatake, Kurenai Yuhi, Asuma Sarutobi, and Might Guy. "We have important matters to discuss."

Only Kakashi did not look confused by Tsunade's words.

"Two days ago, the mission to bring Sasuke Uchiha back to the village ended in failure. But, that's not the only thing that happened," Tsunade said with sadness in her eyes. "Naruto Uzumaki lost control while he was using the Nine-Tailed Demon Fox's chakra. This caused him to attack Kakashi when he showed up to bring him back to the village. As a result of this, I had no choice but to revoke Naruto's status as a Leaf shinobi until he displayed the necessary control to safely do missions. I also placed restrictions on him in order to prevent him from leaving the village."

Kurenai, Asuma, and Guy all looked shocked by what they were told.

"Unfortunately, Naruto left the village before I could arrange to have ANBU keep an eye on him or have the Barrier Team add an alert in order to prevent him from leaving the village undetected," Tsunade said with a sigh. "Furthermore, he used the Multi Shadow Clone Jutsu to leave false trails away from the village. Every chunin or higher member of the Inuzuka clan is currently searching for Naruto. They will search for forty-eight more hours before returning. As it is, it's believed that he is no longer in the Land of Fire."

The three jonin that were hearing about the situation for the first time looked at Kakashi sadly.

"Naruto's unwelcome departure leaves us with one major difficulty. We need to explain his removal from the Ninja Corps to your teams," Tsunade said with a frown. "I believe that I might have to revoke the Third's Law as a result."

"Are you sure that's wise?" Kakashi asked immediately. "Telling them that he holds the Nine-Tails and lost control to it, causing him to attack a comrade… it might not be the best thing."

"It might not be the best idea, but what else is there to do? The only other option that I've come up with is to tell everyone that he attacked you in anger, and we had to revoke his status as a ninja because of it," Tsunade said as she looked at the Copy Ninja sadly. "No one would believe that he attacked you in anger though, especially his friends."

"Shikamaru would think it's too troublesome to form a new opinion about Naruto, and Choji wouldn't care about Naruto's burden or that he lost control," Asuma suddenly said. "Ino's a bit more complicated. Inoichi would set her straight about the whole thing though."

"Hinata wouldn't think different of him, despite the full situation. And Kiba would no doubt sympathize with Naruto. After all, he knows what it's like to lose control to his inner beast. All members of his clan can understand that," Kurenai said. "Shino uses logic so heavily that I can predict his reaction. He'd no doubt sympathize with Naruto over having something within him that people judge him for, but he'd also be wary of Naruto because of his lack of control."

"I have no doubt that Lee and Neji will understand Naruto's situation in full without judgment. Tenten will follow her teammates in this," Guy said enthusiastically.

Sighing, Kakashi said, "Sakura is unpredictable right now. One of her teammates defected, and the other ended up in a situation where he ceased to be a ninja of the village and left. She's not going to handle this well."

Tsunade nodded her head. "By noon today, the Third Hokage's law will be revoked. Make sure you tell your teams today. It will get around the village before long, after all." She then looked directly at Kakashi. "Oh, and I want you to bring Sakura here. I'll tell her myself. I will also need to inform her that she is to start training under me next week."

That surprised Kakashi more than anything else she had said.

"Given that her teammates are no longer in the village, I believe it would be best for Team Seven to be dissolved. Sakura will undergo training in medical ninjutsu, so she will be able to work with her former classmates on missions in a support role. In addition to that, I'll be able to keep an eye on her," Tsunade explained. "Now, I believe we are done here. You are all dismissed."

Nodding, all four jonin left the room.

* * *

About an hour later, Kakashi arrived back at the Hokage's office with Sakura.

Inwardly, he sighed as he their meeting with the Hokage was about to begin. She had been asking him where Naruto was ever since the rest of the Sasuke Retrieval Team arrived home, barring the period of time when he was out searching for Naruto.

"It's time to begin," Tsunade said, looking at the pair intently.

"Shouldn't we wait for Naruto?" Sakura asked. "He's part of Team Seven, after all."

"Naruto isn't in the village," Tsunade said quietly.

"Is he on a mission?" Sakura asked, her eyes filled with desperate hope.

"No, he's not," Tsunade answered. "Naruto Uzumaki was removed from the Ninja Corps because he lost control after the mission to retrieve Sasuke Uchiha ended in failure."

"What are you talking about?" Sakura asked, her eyes beginning to water.

"There are things that you don't know about Naruto. The biggest thing is that he is a living prison. Tailed beasts cannot be truly killed, not even by men such as the Fourth Hokage. All along, Naruto has held the Nine-Tailed Demon Fox within him. In a way, he is a scroll and the Nine-Tails is a kunai. That analogy doesn't do the truth justice though. You see, Naruto can access the Nine-Tails chakra at will. When he accesses its chakra, it can influence him," Tsunade explained.

"When you say that he lost control, you mean that it took over?" Sakura asked with tears in her eyes.

"It took over temporarily, and he attacked me when he was in that state," Kakashi answered quietly.

At hearing that, Sakura began to cry. Unfortunately, that was not the end of everything.

"I was forced to remove him from the Ninja Corps and restrict him to the village, but it seems only the former stuck. He left the village that night, and we have been unable to find him," Tsunade said. "Because of everything that has happened, Team Seven is to be disbanded. Kakashi will resume regular jonin duties, and you will become my apprentice. From what I gather, you'd be an excellent medic."

Through her tears, Sakura said, "Thank you, Lady Hokage."

Both shinobi knew what she was thinking as she said that too.

She intended to get strong enough through the training to bring Sasuke and Naruto back.

Neither one of them could bring themselves to discourage her.

* * *

"Today, I'd like to tell you about jinchuriki," Kurenai Yuhi said as she sat with her team at one of the various training grounds in the Hidden Leaf Village.

"A jinchuriki is a human that has a tailed beast sealed within him or her, is it not?" Shino asked.

"That's correct," Kurenai said, not surprised that Shino knew of the term.

"Why would anyone seal a tailed beast within someone? Couldn't they just kill the tailed beat like the Fourth did?" Kiba asked.

"Jinchuriki are thought of as living weapons. That is how the history books speak of them, at least," Shino suddenly said. "I am told that Gaara of the Desert was one. Such power would benefit any village."

Kiba and Hinata shivered at that information.

"The Fourth Hokage did not kill the Nine-Tails," Kurenai said carefully. "Tailed beasts are living constructs of chakra. The only way to deal with one is to seal it away."

"The Nine-Tailed Demon Fox has a jinchuriki then," Shino said evenly.

"Yes, and you all know who him," Kurenai said with a nod of agreement. "The Nine-Tails was sealed inside Naruto Uzumaki, your former classmate."

As expected, Shino simply nodded his head. It was clear that he had determined that there was nothing wrong with it, logically.

Hinata looked shocked at the news that her crush contained such a powerful entity. She did not seem to change her opinion of him at the news though.

"So not all jinchuriki are insane?" KIba asked, almost sounding relieved. "If some are like Naruto, we don't have to worry too much, I guess. It's definitely better than having ones like that Gaara guy."

Kurenai almost laughed at Kiba's statement. It even seemed to make Hinata smile.

"Something's happened," Shino said, drawing everyone's attention. "You wouldn't tell us about a secret like this nearly thirteen years after it was made without a good reason."

Kurenai nodded her head sadly. "Naruto used the Nine-Tailed Demon Fox's chakra when he fought Sasuke Uchiha at the Valley of the End. At the end of the fight, the fox's malicious will gave Naruto some trouble, allowing Sasuke to get away. This caused Naruto to lose control to the fox temporarily. Kakashi Hatake showed up when he was in that state and Naruto attacked him. As a result of this, Naruto was removed from the Ninja Corps until he could gain the emotional control. He was also restricted to the village during this time."

"It seems fairly logical," Shino said with a nod.

"Yeah, but Naruto doesn't give a damn about logic," Kiba said as he shook his head. "Knowing him, he's going to feel like he's backed in a corner. The Third Hokage was like a grandfather to him, and he thought of Sasuke as his best friend. With the Hokage dead and Sasuke's betrayal added on to his removal from the Ninja Corps, Naruto is going to run. When you feel like the whole world's turned against you, you have to fight back however you can. Running fights back against the only part of the whole thing that he can fight."

"Perhaps Lady Tsunade should have asked you to be her advisor on the matter," Kurenai muttered. Clearing her throat, she said, "Naruto Uzumaki left within a couple hours of that. Every chunin and above of the Inuzuka clan is currently searching for him. It's believed that he is no longer in the Land of Fire."

Everyone looked shocked to hear that, especially Kiba.

"I thought the clan compound looked empty yesterday," he muttered.

* * *

"And that's the whole truth," Asuma finished, looking at his students as he finished telling them about Naruto's status as a jinchuriki and his departure from the village after his status as a Leaf ninja was revoked.

The team was in Choji's hospital room. He was still recovering from the damage that he sustained thanks to the Akimichi clan's special food pills.

"This is my fault," Shikamaru said with a sigh. "I let him go off on his own. If I had told him to stay with me, he wouldn't have lost control. The end result would have been the same with the exception of him losing control."

"It's not your fault," Choji said with a weak smile. "Naruto wouldn't have listened to you. He's a great guy, especially now that we can see everything he's been through, but he's not one to follow orders very well."

As the two boys talked, Ino looked conflicted. It was clear that she was not sure what to think about everything that they had heard.

"Can we even be sure that Naruto has been in control all this time?" Ino suddenly asked. "What if the fox took him over a while back and has just been pretending to be Naruto? What if he didn't lose control after Sasuke got away, but he really just revealed who has actually been in control all this time?"

"The fox's will is directly tied to its chakra," Asuma said seriously. "Ino, you're a sensor, just like your entire clan is. Did his chakra feel as malicious as that Gaara boy's chakra? If not, then Naruto has been in control. Without the fox's chakra flowing through him, it can't stay in control."

Ino only looked a little reassured at that.

"Naruto saved the village from Gaara, and he brought Lady Tsunade back to become the Hokage. It was because of her that Lee's injuries were healed and Kakashi-sensei woke from the coma that he fell into when he fought Itachi Uchiha. If Naruto was really the fox, he would never have done those things," Shikamaru said. "I don't have a doubt that that Naruto has been in control all along."

Ino nodded her head, though her eyes revealed that she was still not convinced on the matter.

"Ino, I'd like you to head to the Administration Building," Asuma suddenly said. "Sakura is in a meeting with the Hokage right now. Her team has been disbanded, so she'll need a friend to talk to."

"Yes Asuma-sensei," Ino said as she rose to her feet and left.

Asuma noted that that was the first time since he told them the truth that she did not look nervous.

"Shikamaru, let's go and get something to eat. Then, you can come back and hang out with Choji," Asuma said, inwardly laughing when Choji groaned at the mention of eating.

"Sounds good sensei," Shikamaru said with a chuckle.

* * *

"And the recent events diminished his Flames of Youth so much that he had to leave the village to rekindle them. Even then, it is unknown if he will return," Guy said, finishing his explanation.

Neji and Tenten shared a look that said, "What in the hell is he on?"

They did manage to get the gist of it, but they still planned on seeking out Kakashi Hatake for a better explanation. Between the flowery metaphors and rants about the Flames of Youth, the only things that they had taken away from the explanation were that Naruto was a jinchuriki and that he had left the village.

From what they understood, they could see that Naruto truly had a heavy burden though. It was easy to imagine that a burden that heavy could break a person.

Lee, however, had fire in his eyes and was vowing that he would train ten times as hard so that he could seek Naruto out, rekindle his Flames of Youth, and would bring him back to the village.

* * *

Within hours, the news of Naruto's status as a jinchuriki got around the village, along with the events that caused him to leave.

Feelings were mixed among the village, but more than half of the people in the village actually worried about him.

None did more so than Teuchi, Ayame, Iruka Umino, and the Konohamaru Corps.

Of everyone in the village, Konohamaru and his friends actually took all of the news very well. They had actually come to respect Naruto even more for the burden that he carried and felt that Tsunade had been wrong when she revoked his status as a ninja of the village.

They could not see why anyone would fault Naruto for losing control when using the Nine-Tailed Demon Fox's power. It was said to wield unfathomable power, after all.

* * *

In the Land of Waves, Naruto was unaware that his secret was out and that his friends knew that he had run away.

In fact, he was mostly oblivious to all but one thing: the bag of groceries in his hand.

It had taken him a few hours to come to the conclusion that he needed to give something back to the Land of Waves. After all, he could have anything he wanted in the land without paying a single ryo for it. In fact, he had been given his new attire from a seamstress, and she had refused to accept payment.

Thus, he was walked down the street in black sandals, black pants, and an orange short sleeve shirt with a black spiral on the front of it as he did the equivalent of D-rank missions for the people of the town for free.

Anyone who knew Naruto knew that he was not generally happy to do such manual labor, especially not when he had fought against the likes of Haku, Neji, Gaara, and Kimimaro. However, it was not the worst thing that he could imagine doing either. It was not like they needed him to do anything more ninja-ish, after all.

So wish that, he continued on his way.

* * *

Tayuya took a deep breath as she peeked out from the tree she was standing behind.

A hundred yards away, a single Leaf ninja was walking with a medium sized dog at his side. By the red marking on his face, she recognized him as a member of the Inuzuka clan.

A weak breeze was blowing towards her, so her scent remained undetected by the dog. Even then, she had to keep her chakra suppressed to stay unnoticed.

_Damn this fucktard. I specifically decided to travel at night in order to avoid these guys, and now they're searching after the sun's gone down. Karma's a bitch._

She carefully left her spot in a crouch, careful not to step on a twig while keeping her eyes on the nearby Leaf ninja. She momentarily considered activating her curse mark, but she knew that the dog would sense the malicious chakra. Plus, she was going to try not to depend on it anymore. She was no longer Orochimaru's follower, so she did not want to depend on his strength.

She managed to get halfway to the ninja, before he turned and saw her, causing her mind to fill with cursing.

"Hey, what are you doing out here?" he asked as he walked towards her. "It's late out. You shouldn't travel so late. Someone might think a pretty girl like you is a spy, or bandits might find you."

Tayuya wanted to roll her eyes at that, but she was actually quite thankful that he did not realize who her allegiance had been to. In daylight, the ninja most likely would have recognized it as being a torn tunic that some of Orochimaru's henchmen wore.

Working up her best _frightened girl_ voice, Tayuya said, "I'm s-sorry. I was just s-so scared. There were ninja everyone. I t-thought it might be a g-good idea to travel when no one was out. Some of you ninja s-scare me." She began to act like she was starting to cry at the end to boost the dramatics.

Seeing him slowly walk up to her, she fought back a grin. _Hook. Line. Sinker._

"It's okay. I'll protect you. Just come with me and-" the Leaf ninja began as he got near her.

And then, Tayuya sprang into action. She hit him with a round house kick faster than he could even process the movement. She hit him in the side of the head, instantly knocking him out.

As her meet touched the ground again, her attention was on the dog that had just leapt towards her.

She quickly brought her right leg up into the air and brought it down in an axe kick. Her aim was perfect, and she hit the dog on the top of the head.

After the ninja and the ninja dog were taken care of, she checked both of their pulses and exhaled a deep breath when she found that they were both alive. Furthermore, the dog didn't sustain any real damage from her kick.

Tayuya may have been a killer for Orochimaru on several occasions, but she did not relish killing anything, especially animals.

_That Snake bastard said the Inuzuka clan has the mentality of a clan of dogs. He's not going to risk letting his buddies know that a girl kicked his ass._

With a grin, Tayuya removed his shuriken holster and his kunai holster from his right leg. She then strapped them to her leg and left.

Now that she was armed, she knew that she could not let anyone see her. After all, any Leaf ninja that saw her would not mistake her for a wandering civilian now that she had the holsters at her leg.

_Time to get a move on._

* * *

Author's Note: And that's another chapter done.

As you no doubt noticed, it was really just eight kind of short scenes put together. Naruto's scene gave me some trouble, especially since nothing really happened in it except for him reflecting back.

Anyways, Naruto's life as a freelance ninja will be picking up soon.

Oh, and I wanted to address this just in case someone asks.

Naruto's peers do see him in a more positive light now, excluding Ino. However, they will also be wary of him. His lack of control will taint their interactions with him in future arcs. I'll stop there since I don't want to say too much.


	4. Bandit Trouble

So how many people got nervous when I didn't update yesterday? Usually, that's a sign of trouble, but I was actually occupied with certain things. I watched the Sunday Matinee of Captain America, which was totally epic in my opinion. I actually didn't even like him before I saw the movie. Oh, and I also read another awesome Naruto/Tayuya fic, Naruto Makaze: Birth of a Legend. I definitely recommend it to anyone who is interested. In it, Naruto is a mercenary, but it's quite a bit different from my story.

Now, on to the chapter.

* * *

Disclaimer: I do not own Naruto.

* * *

**New Destiny Arc**

**4. Bandit Trouble**

Naruto looked around the area around him momentarily. It was the same place where Kakashi had taught him, Sakura, and Sasuke how to climb trees with their chakra. He relished in the nostalgia before he took a deep breath and began to focus all of his attention to his right hand.

It had been three days since he had begun to do chores for the people of the Land of Waves, which meant that it had been two days since he had felt that he was recovered enough to resume his training.

Contrary to popular belief, Naruto was not an idiot. His intelligence was average at best, but that was a far cry from being an idiot. As such, he knew that the Hidden Leaf Village was looking for them. In fact, he knew that they would most likely never stop looking for him. The power that resided within him was too great for them not to go after.

As it was, the reason that he had been restricted to the village had been all about the Nine-Tails.

He wanted to become strong enough that he could handle anyone that caught up with him, preferably without killing them. That was why he planned on focusing on his training as much as he could.

Still, things were not going to be easy. He had no one to teach him, and it was not as though he had a jutsu library handy.

The day before, when he had begun his training, he had thought long and hard about what he could train. After over an hour of thinking about it, he had realized that there was only one bit of training that he could do by himself that would fix a rather large weakness.

And so, he began to attempt to figure out how to form the Rasengan without the aid of a shadow clone, or even a second hand. He had done it when he was in his one-tailed state, so he knew that he could do it, but replicating it in his regular form was quite difficult.

Because of his difficulty in that endeavor, he began to work on the training a bit different. That was why he had one water balloon in his right hand, while five more sat on the ground next to him and just as many rubber balls sat next to those.

If he could not figure out how to do it with one hand directly, then he relearning it from the beginning with one hand seemed to be the only option.

As he closed his eyes, the water within the balloon began to move in multiple directions at the same. He kept the flow of chakra weak at first, knowing that it would not do the job. When he increased the flow of the chakra, however, the water inside began to spin around wildly.

The balloon exploded within moments, showering him with water.

_It's definitely easier once you know the secrets behind each step._

Kneeling down, Naruto picked up another water balloon and began to repeat the first step without even standing back up.

He repeated the process for each water balloon, putting in the minimum amount of chakra required to make the balloon explode.

_The first step is about control. The second step is about power. The third step is about combining the first two._

Naruto rose to his feet finally, but he had a rubber ball in his hand when he did so. Once again, he began to mold a large amount of chakra. This time, however, he molded ten times more chakra than he had used on any of the water balloons. He grimaced as a hole as wide as his pinky appeared in the rubber ball, causing it to pop.

_That's not the limit to my power. Screw it, I'm going to put everything I've got into it._

With that thought, he kneeled down and picked up another rubber ball.

Closing his eyes, he began to mold chakra. His plan to put in everything he had faded as he molded more than twice what he had in his last attempt. It was less than twenty-five percent of what he could generate.

After only a few more seconds of molding chakra, he sent it into the rubber ball and began to spin it around in multiple directions.

The ball exploded with the force of a paper bomb, knocking him a few feet back and burning his hand with pure chakra.

_Damn it, that hurts! I think that's good for today._

Slowly rising to his feet, he walked over to the remaining balls and picked them up before he headed back to Tazuna's house.

* * *

When Naruto got near Tazuna's house, he saw that the old bridge builder was talking to one of the men that had helped with the construction of the Great Naruto Bridge. Unless he was mistaken, the man's name was Giichi.

As he neared them, they began to talk. It was clear that they did not see him though.

"I'm telling you, this spells trouble. We might have to ask the Hidden Leaf Village for help. Now that we have the bridge, we don't have to rely on our port, but the bridge might as well not be there with those bandits on the other side of it," Giichi said, shaking his head. "They keep charging a _toll_ to anyone who wants to use the bridge."

"We can't risk them finding out that Naruto's here," Tazuna said with a heavy sigh.

"In that case, we'll need to round some men up and scare them off," Giichi said, clearly seeing Tazuna's point.

"I'll take care of them," Naruto said as he came closer to them. They immediately looked shocked, reaffirming Naruto's suspicion that they had not seen him before he spoke.

"We can't ask you to do that," Tazuna said immediately.

"I'm the so-called Hero of Wave, aren't I?" Naruto asked with a small smile. "You've got a problem, so I'll deal with it. I won't let anyone die doing what I'm trained to do."

"Thank you," Giichi said with relief clear in his eyes. "You don't know how much this will mean to everyone."

Naruto nodded without saying a word to the man. He then handed the remaining three rubber balls to Tazuna. "Put these up in my room please. I'll go and handle them now."

"Be careful," Tazuna said, nodding his head.

"Compared to Zabuza and Haku, these guys will be a piece of cake," Naruto said with a dismissive laugh.

Walking away from the pair of men, Naruto's thoughts drifted to a new direction.

_I can't keep doing this. If I wasn't around, they could just send someone to visit the Hidden Leaf Village and ask for a team to deal with it. Sure, it would cost them money, but it wouldn't cost them lives. What if I hadn't overheard them? I just know someone would've died._

* * *

Naruto carefully wrapped a paper bomb around the handle of one of his kunai as he stood atop the water underneath the Great Naruto Bridge.

From what he figured, the bandits would run off if they saw him approaching, and they would come back after he left. Thus, he had walked underneath the bridge until he was almost to the end. All he would need to do was climb up and attack before they saw him coming. They would have no choice but to fight him, and his skills as a ninja would allow him to overcome mere thugs.

So he quickly jumped and used chakra to catch on to one of the support beams of the bridge. He then scaled it as fast as he could, staying on the inside until he reached the top. It allowed him to remain hidden as he climbed.

Once he reached the top, he quickly move to the outside and jumped over the bridge's railing, letting him land on the bridge about ten yards away from the canopy.

He rushed towards them, diving into a roll that put him just past the group of bandits that her set up there. There were ten bandits total, but Naruto's mind was running wild as he recognized two of them.

The swordsmen bodyguards that were in Gato's employ, Waraji and Zori, were almong them.

"What do you think you're doing here?" Naruto asked as he drew the kunai that he had prepared earlier. His plan had changed slightly with them there.

"It's that kid that got us last time," Waraji said as he drew his katana. "Kill the runt."

With that, eight of the bandits charged towards Naruto, leaving Waraji and Zori to watch the fight.

_They're probably going to try to have their men tire me out so they can finish me off. Well, that's not going to happen._

Naruto's left hand went to his hip pouch as the bandits rushed towards them. He remained completely still until they were almost on him. And then, he used a chakra enhanced jump to get quite a ways above them.

As he ascended above them, he did not attack though.

His attack had been laid in place even before then.

Only one of the bandits noticed the five small crumpled up pieces of paper where Naruto had been standing. More precisely, only he had noticed the hissing sound coming from them.

Unfortunately for them, bandits did not deal with ninja very often. If they had, they would have known what a paper bomb sounded like before they found out.

When they found out, they were dead.

The explosion that resulted from the five paper bombs that Naruto had crumpled up and dropped behind him propelled him a little higher in the air. In addition to that, it knocked Waraji and Zori down.

As he reached the apex, Naruto reared back and threw his kunai with all the force he had.

It sunk into Waraji's ribs with ease. And then, hissing began to come from the handle of the kunai.

Naruto immediately knew that he would be in the blast radius of the paper bomb if he fell to the ground where he was, so he formed his signature hand sign and created a shadow clone next to him. It did not even need to be told what to do. It grabbed onto Naruto's arm and spun around, throwing him away from the bridge.

He landed with a back flip, just in time to see Waraji's abdomen explode and his shadow clone to dispel.

Zori, who had jumped out of the way just in time to dodge the blast, drew his sword with fury in his eyes. "I'm going to kill you," he called out as he ran towards Naruto with his katana drawn back.

Time seemed to slow down as Zori swung his katana in a horizontal arc at Naruto's neck. He ducked underneath the blade and spun behind the swordsmen. Naruto jumped a few feet into the air placed both of his hands on Zori's forehead from behind, and sent both of his feet into the middle of the man's spine.

With the single movement, Naruto broke his neck and his spine.

As Naruto did a back flip away from the corpse, he heard clapping. The sound startled him and made him feel sick to his stomach. Killing those men had been something that had to be done, but he could not understand how anyone could clap at seeing such a thing.

Turning to the source of the noise, Naruto's hand found its way to his kunai holster and drew one from it.

As she stepped out from the tree she had been standing behind, he recognized the tunic she wore, even torn as it was. That was not all he recognized either. She was missing her hat, her belt, and the bottom part of her tunic, but he could never forget that girl.

"What are you doing here, Sound ninja?" Naruto snarled.

Realization dawned in the girl's eyes as she recognized him too. "You're that blond shithead that was with that damned rat."

"I'm not going to ask again. What are you doing here?" Naruto asked as he prepared to attack.

Her eyes became analytical as she watched him. "I'm going to go across that bridge behind you."

Naruto's eyes grew cold at that. "I'll kill you if you try to harm anyone. It's my job to protect them, and I'll do that, no matter how strong you might be."

The girl's mouth turned downward slight, a small frown showing itself. "Perhaps you're not too bright or something. That's the Land of Waves, not your village."

"I don't have a village," Naruto said, touching his left thumb to his forehead. "I've been kicked out of the Ninja Corps in the Hidden Leaf Village. As the Hero of Wave, I still can't let an enemy, a Sound ninja no less, walk take a single step on the Great Naruto Bridge."

The girl's frown grew at that. She stayed silent for a few moments after hearing his words. "Then we're not enemies. If you're seriously telling me that you were kicked out of your village's Ninja Corps, which is pretty damn rare, then you can cool it. You and your friends killed the rest of my group. That damned snake is going to kill me if I show my face around any of his bases. As far as he knows, I'm dead, and I intend to keep it that way. I can't exactly stay hidden if I'm killing people, can I shithead?"

Naruto thought about it for a moment. She was clearly nervous, and he had no doubt that Orochimaru would kill his shinobi for failing him. She could have lied to him, but he had a gut feeling that she was telling the truth.

"Give me your word you won't cause any problems," Naruto said with a serious look in his eyes.

"Fine, I give my word I won't cause any problems," she said grudgingly.

"Don't make me regret trusting you," Naruto said as he put his kunai away and began to walk towards the bridge. "Come on. I'll show you around."

"Why in the hell would I want you to show me around, shithead?" she asked in disbelief.

"Any ninja with half a brain is going to recognize you for a Sound ninja," Naruto remarked. "I've been here long enough to know where you can get some new clothes."

"I managed to fool a member of your old village's Inuzuka clan," she retorted.

"Again, any ninja with half a brain is going to recognize you for a Sound ninja. An Inuzuka is born with half a brain, but he has to share it with his dog," Naruto joked.

A ghost of a smile showed itself on her face at the joke, but she quickly regained her composure. "So were you really kicked out of your old village's Ninja Corp, or did you go rogue?"

Naruto continued to walk as he heard the question. Once he heard her footsteps behind him, he answered her. "I wouldn't have gone rogue. I'd be a pretty big hypocrite for trying to make Sasuke come back when I was willing to just walk away. No, I was kicked out of the Ninja Corp for something that happened during that mission."

She nodded her head, accepting that answer. It was vague but logical.

"So what's your name?" he asked. "Mine's Naruto, but I get the feeling you're not going to call me by it."

"Damn straight, shithead," she said. "I guess it won't hurt to tell you what it is. After all, I'll have to kill you if you come up with a nickname. I'm Tayuya."

"Well Tayuya, do you have any money on you?" Naruto asked, mentally sighing at her nickname for him.

She frowned at that. "No, my last boss didn't exactly pay his ninja. Fucking cheapskate," she answered.

"I'll handle everything this time," Naruto said, mentally sighing at the thought of using his status as the Hero of Wave to get the redhead some new clothes and a room for the night. "You'll have to get some ryo of your own if you don't want to sleep in the woods after tonight."

"Yeah, yeah, I'm only accepting your help since you'll throw a bitch fit if I steal some clothes," she said, rolling her eyes.

"You are by far the most foul mouthed girl I've ever met," Naruto said, shaking his head in disbelief.

"Aww, that's sweet. Now I'm blushing," Tayuya replied sarcastically.

_Women are insane._ Little did he know how often he would think those thoughts in the coming years.

* * *

Several hours later, Naruto walked out of one of the few hotels in the city, where he had told Tayuya to wait for him, which she surprisingly did.

Upon arriving in town, he had taken her to the store to get her some more clothes. He had ended up getting her some new black sandals, black shorts, and a sleeveless black shirt from the store. It seemed that she was rather picky. It did not help that those were the only black garments they had in women's sizes. She had nearly knocked him out when he suggested she wear pink.

After that, he had gotten them both something to eat, which she had accepted without any persuasion. She had even thanked him, provided that "thanks shithead" was a valid way to thank someone.

Finally, he had come to get her a room for the night.

Upon arriving in front of her, Tayuya's eyes focused on him with surprising intensity, but she did not say anything immediately.

He handed her a key and said, "You have room number one hundred-three for the night. You might be able to get that time extended if you help the owner -"

"Shithead, why do you keep doing this? I had no choice but to accept the clothes. I was too hungry to refuse the food. But I told you I could find my own place to sleep. Why do you keep trying to help me? Why won't you just leave me alone? We're not friends. We were enemies not too long ago."

Naruto turned away from her and looked up at the setting sun. "We're the same. I realized it not long after we met on the other side of the bridge. We both have an inner darkness and know the pain of being alone."

"Shut up! You don't know anything about me!" Tayuya said, anger clear in her eyes.

Naruto knew that he had touched a nerve, but he was not one to back off. "It's addictive, isn't it? You have that dark chakra within you. It feels like it belongs to you, but it's separate and feels completely different. You know if you accept it, you gain so much power that it makes you giddy. But if you accept it, you begin to lose yourself to its darkness. Even that trade-off isn't enough to get you to stop using it though."

Tayuya looked shocked at his words, her right hand going to the back of her neck.

Naruto set the room key on the bench next to her and began to walk away. As he did, he said, "I'll be around. Have a good night."

* * *

Naruto walked into Tazuna's house about fifteen minutes later.

"Naruto, we were wondering where you were!" Tazuna exclaimed, worry in his eyes. "We hadn't heard back from you since you left to deal with the bandits."

"Sorry about that," Naruto said, running his head sheepishly. "After I dealt with them, I ran into someone I met once. We had some catching up to do."

"Do you want to tell us about the fight?" Tazuna asked, no doubt remembering the ninja fights he had seen in the past year.

"I'd rather not. I'm still not sure what to think of everything," Naruto said with a sigh. "I'm going to go to bed. I'll see you guys tomorrow."

With that, Naruto walked upstairs, the faces of the men he killed flashing to his mind as he prepared to go to sleep.

* * *

Author's Note: Thanks for reading and reviewing.

As you may have noticed, I just added the arc name above the chapter title. I figured I'd start doing that for this fic.

Oh, and I actually have a poll that I'd like everyone to look at.

I'm trying to decide if I should have a training arc after the second arc, which would enable Naruto and Tayuya to grow more as shinobi before they start doing missions. Usually, I use polls to figure out your opinions and then I make my own decision. This time, I'll actually be using the winning vote.

Again, only votes in the poll will be counted.


	5. A Proposition

Disclaimer: I do not own Naruto.

* * *

**New Destiny Arc**

**5. The Proposition**

Naruto let out a yawn as he walked through the forest towards his training spot as he had done every morning since he took out the bandits on the other side of the Great Naruto Bridge.

Every day, he trained until lunch time, ate at Tazuna's house, did the equivalent of D-rank missions around town until dinner time, and ate again at Tazuna's house. The rest of his nights were generally spent talking to the bridge builder or his grandson and sleeping.

Looking down at his right hand, he frowned. It was burnt with chakra still, though the current chakra burn was fresh. He had been pushing himself hard, and he still could not find the minimum amount of chakra required to pop the rubber ball. He knew that he had a tendency to overload his jutsu, which made them ineffective.

He did not want the Rasengan to be ineffective.

_I should be able to master the Rasengan in three weeks. The last step is always harder than the first two._

He was broken from his thoughts as he entered the clearing that he normally trained in and saw Tayuya leaning against a tree, looking towards him.

It was the first time that he had seen the redhead since she snapped at him and he told her just how similar they were.

"You're right," she suddenly said, catching his attention immediately. "We're the same. I've been watching you for the past week, and I think I finally understand you a little."

"Do you?" Naruto asked, hiding his surprise that she had been watching him. He knew from that moment that she had impressive stealth skills.

"Yeah, I do," Tayuya said as she took a few steps closer to him. "And that's why I know you're not happy here. You can deny it all you want and say that you are happy, but you can't be. You spend your days accomplishing very little in your training, and then you get to spend the rest of your days carrying groceries and painting fences. If you're anything like me, you have to hate it. You've had a taste of what it means to truly be a ninja. I heard that you even fought against Gaara of the Sand when your village was invaded. How can you be satisfied with this pathetic excuse for a life when you can have so much more?"

Naruto frowned, looking away from her. The simple truth of the matter was that she was correct. He was not happy with the way he spent his days. Still, that did not make the life he currently had a bad one. He stayed in the Land of Waves because he had people that cared about him there, not because of any opportunities it would present to him as a shinobi.

"And what would you have me do?" Naruto asked. "My village is hunting me. If I don't stay in hiding, they will probably find me and force me to come back."

"I have a similar problem," Tayuya remarked dryly. "Even so, why would you want to live like this? The whole point in hiding from them is so you can live your own life, isn't it? Well, I don't know how you could call this living your own life."

Naruto closed his eyes as he thought about what she said. He honestly could not say that what he was currently doing was any better than what he had waiting for him back in the Hidden Leaf Village.

_If only there was a way to have the life I had back in the village but without the village itself. Doing real missions, training, and actually making a difference… it's so much better than this. And without the village, I wouldn't have to be around people that hate me._ Thoughts of him going to take out the bandits a week earlier suddenly came to mind. That had been a real mission, albeit an easy one. Realization suddenly dawned in his eyes. _Maybe there is a way after all._

"You're right," Naruto said, looking at her. "I know what I have to do now. I'm going to be a real ninja. I might not have a village anymore, but that doesn't mean I can't do real missions."

"You're going to do what rogue ninja do?" Tayuya asked, surprised. "Except you won't be a rogue ninja, so you'll be some kind of freelance ninja, I suppose."

"Yeah, that's exactly what I'm going to do. I'll do missions anywhere and do my best to stay one step ahead of my pursuers at the same time," Naruto said with determination in his eyes. "And I want you to join me. With teamwork, we can accomplish anything. Be my partner, and Orochimaru won't get to you without going through me." He stuck his hand out at that point.

Tayuya was taken aback by Naruto's words. She had to admit that it sounded like a good deal. Neither one of them wanted to live a life without fulfillment.

She took his hand a few moments later. "Fine, we'll be equal partners. If you're willing to fight against Orochimaru if he comes after me, then I can fight against any of your old comrades if they come after you, even the Hokage."

Naruto smiled at that as they broke the handshake. "Well then, I'd like to tell you a story."

Tayuya raised an eyebrow at that.

"Has anyone told you why I'm called _the Hero of Wave_?" he asked.

"No, I thought you were just bullshiting me. Are you really called that?" Tayuya asked.

"Yeah," Naruto said with a chuckle. "A month after I became a genin, my team went on a mission to this country. We had to escort a master bridge builder here and protect him while he finished his bridge. Unfortunately, he only requested a C-rank mission, and he had three chunin level shinobi and one jonin level shinobi after him."

"So your team was just out of the Academy, and you had to fight overwhelming odds?" Tayuya asked, interested in the story.

"Yeah, that's about right," Naruto answered. "On the way to the Land of Waves, we were attacked by these two rogue ninja. I don't know their names, but Kakashi-sensei called them the Demon Brothers of the Hidden Mist."

"I've heard of them. They're good at what they do, even if they are not too strong individually," Tayuya remarked. "But why did your sensei continue with the mission after he knew that ninja were after the client? That doesn't seem like a very smart decision."

"It was actually because of me that we didn't turn back. I froze in the fight, and I swore that I wouldn't give up or back down. Sasuke was all too happy to side with me on that one. He was always obsessed about proving his strength, now that I think about it," Naruto said with a light hearted chuckle. "We reached the Land of Waves before we were attacked again. We were actually almost to our client's house. Just thinking about that fight sends chills down my spine."

"Why is that?" Tayuya asked. Hearing that a fight unnerved the guy who beat Gaara meant that the fight had to be incredibly dangerous.

"The jonin level ninja that had been hired to go after our client was Zabuza Momochi, the Demon of the Hidden Mist," Naruto answered.

Tayuya's eyes widened at that. While Zabuza was not on the same level as Orochimaru, he was certainly a powerful that could not be beaten easily.

"Kakashi-sensei fought him alone at first," Naruto said, beginning to tell her about the rest of his team's first fight with Zabuza.

By the end of it, he could easily see that Tayuya was impressed by what he had done.

"As impressive as that is, how did you come to be known as _the Hero of Wave_? Your sensei did more than you did," Tayuya said.

"That was just our first fight with Zabuza," Naruto said, shaking his head. "The masked ninja was one of Zabuza's accomplices. He only intervened in order to save Zabuza. We ended up fighting both of them a week later."

"So you became known as _the Hero of Wave_ because of that second fight?" she asked.

Naruto laughed and shook his head. "I'm not known as _the Hero of Wave_ because of either fight. I'm known as it because I woke up late on the day of the second fight, which put me at being near the house when these two swordsman showed up to take our client's daughter hostage. They worked for the same client that Zabuza was working for. Anyways, I saved her and tied up the swordsman, and I somehow inspired her son. I'm called _the Hero of Wave_ because I inspired him to fight back for his freedom. But that's just it. I only inspired one boy. He inspired the rest of the town."

"Seriously, that's it?" Tayuya asked, shocked. "They call you a hero for that?"

"That was my first reaction," Naruto said with a laugh. "But anyways, the reason I wanted to tell you this story was because it explains how Zabuza died. Coincidentally, it also explains how I know where his sword is."

Tayuya looked startled at that. "Shithead, do you know how much that sword is worth?"

"No," Naruto replied, not even surprised by the use of the nickname.

"We could sell it to any hidden village for more than ten million ryo," Tayuya said, making his eyes widen. "Tell me, did you kill Zabuza or his accomplice?" She sighed when Naruto shook his head. "Well, you could lie and tell someone in the Hidden Mist Village that you killed them, and they'd probably give us the bounties on both ninja. But I get the feeling that you won't be willing to lie, so we can probably just sell the directions to their bodies to them. It'll be a much smaller amount, but it'll be better than nothing."

"What are we going to do with more than ten million ryo?" Naruto asked.

"Anything we want to," Tayuya replied. "Naturally, partners share their money equally."

_Well, I guess it could be worse. I did ask her to be my partner, so sharing the money isn't too bad._

"Hey Tayuya, can you create storage seals?" Naruto suddenly asked. "I don't know how to create them, and Zabuza's sword is huge."

"You don't know how to create a simple storage scroll?" Tayuya asked in disbelief. She sighed when he shook his head. "Give me a scroll and some ink, and then leave one of those shadow clones that you're always creating with me. It can take me to where the sword is while you see what you can do about getting us to the Land of Water. We'll need to go by boat."

Naruto created a shadow clone immediately. He then handed it a scroll and a jar of ink before he made his way to Tazuna's house.

* * *

Approximately two hours later, Naruto and Tayuya were standing aboard a wooden merchant ship that had just set sail towards the Land of Water.

"So shithead, how exactly did you get them to let us aboard? This isn't the type of ship that people take when they need to go to another country," Tayuya asked.

Naruto glanced at her from his spot at the railing of the ship. "Well, they didn't have any passenger boats headed for the Land of Water. Most people who want to go to the Land of Water go through the Land of Fire first. We both have good reasons for not wanting to do that though, so we're going the long way. The only boats that go straight from the Land of Waves and the Land of Water are merchant ships, which actually have to go around the Land of Tea."

Tayuya groaned at hearing that. Thinking back to her mental map, she realized that the Land of Waves being south of the Land of Fire did not allow a direct path to exist between the two countries.

"And they're letting us ride with them because we're ninja. If anyone attacks them, we have a good reason to step in," Naruto added.

"So we're guards," Tayuya said, shaking her head. "I thought you were just going to use your status as _the Hero of Wave_ to get us a boat."

"Look at the ship's flag," Naruto said, rolling his eyes at his companion.

"Well fuck, I didn't notice that," she said, noticing that the flag that hung from the mast of the ship bore the kanji for water. They were on a boat that was from the Land of Water.

"So what do you think _he_ will do when he finds out you're alive?" Naruto asked.

Tayuya kneeled over the railing next to him at that point. "He'll probably send four-eyes after me. If we both use our dark chakra, we should be able to handle him though." She suddenly looked at Naruto at that moment. "You don't have a curse mark. I'm able to feel curse marks when I'm near someone who has one."

Naruto nodded his head. "Kabuto would be tough, but we could probably take him on together. I hit him with my Rasengan once before. It took him down. He'd be expecting it, but I could probably pull it off."

"Shithead, are you avoiding the subject?" Tayuya asked, staring at him intently.

"I'd rather not talk about it. But I'll tell you this much. What I have is worse than a curse mark," Naruto said, looking away from her.

Tayuya looked away as well. She did not press the subject again.

"It's a good thing we're out of town now," Tayuya said, changing the subject. "If you're really a hero there, I bet a team from the Leaf will be showing up there soon."

She had no idea how right she was.

* * *

In the Village Hidden in the Leaves, Kakashi Hatake walked into the Hokage's office.

"Lady Hokage, I think I know where Naruto is."

Tsunade looked at him in surprise at that. "Where do you think he is?"

"It didn't occur to me until just a little while ago. On our first mission as Team Seven, we went to the Land of Waves. Naruto seemed to inspire the people of the land a great deal, and I heard them refer to him as _the Hero of Wave_ a few times before we left. I don't think he heard it, but it's the only place outside of the Land of Fire that he has ever been to. I'd be willing to bet anything that he headed there," Kakashi explained.

"It's a shame you didn't remember that right from the start," Tsunade said with a sigh. "Okay, go and find Kurenai Yuhi. I want you to go with her team to the Land of Waves to see if he went there. If he's there, seeing his friends might help you bring him back."

"Yes Lady Hokage," Kakashi said before he turned around and left her office.

"Godspeed Kakashi," Tsunade muttered as she picked up a bottle of sake.

* * *

Author's Note: And that's a wrap. Next chapter, Kakashi and Team 8 arrive in the Land of Waves and Naruto arrives in the Land of Water.

Before I bring this to a close, I want to say a few things.

1. Ten ryo equals one dollar in this story. The actual canon exchange rate would be seven and eight hundreths equals one dollar, but I like to KISS. You know, "Keep It Simple, Stupid."

2. Naruto's been a bit more OOC than I intended for him to be. I'm going to chalk it up to the stress of everything getting to him for now. That means that he will likely become more IC before he actually starts having realy character development.

3. There will be a training arc after The Land of Water Arc. 53 people voted for it while 24 people voted against it. It will be a short arc, which is code for two chapters.


	6. The Hidden Mist Village

Author's Note: To clarify, I am using the current map on Narutopedia for this fanfic. That is why the Land of Waves is south of the Land of Fire.

Also, the anime filler arcs, OVA's, and movies that took place before the Sasuke Retrieval Arc are not being used for this story world. This includes the arc that introduced the Sword of the Thunder God (Raijin no Ken), the OVA that introduced Shibuki, and the movie that took place in the Land of Snow.

With that said, I might have the Rain ninja and the rogue Waterfall ninja from the Save the Waterfall Village OVA appear later on. In addition to that, I might use filler characters from later arcs (like Raiga Kurosaki and the Legendary Stupid Brothers) as enemies later on.

* * *

Disclaimer: I do not own Naruto.

* * *

**The Land of Water Arc**

**6. The Hidden Mist Village**

"The Great Naruto Bridge," Kurenai said, looking at the bridge before them. Her eyes went to Kakashi as he looked at it with surprise. It was clear that her students were even more shocked by it than her or Kakashi was.

Though none of the genin were aware of it, it was highly unusual for two jonin and three genin to go on a mission together. In the Hidden Leaf Village, most squads consisted of four people. There were very rare exceptions to it, but they were just that: exceptions.

Still, the whole point of having the genin there was to help persuade Naruto- provided that he was even there in the first place- to come back to the village.

Ironically, the two jonin in the group were the best possible shinobi to be sent against Naruto if he proved uncooperative. They were both skilled with genjutsu, after all.

"What did he do to get a bridge named after him?" Kiba asked.

"He inspired a town," Kakashi replied quietly. "Do you smell his scent?"

Kiba closed his eyes, doing his best to remember Naruto's scent. Though he could smell lingering scents nearly as well as a ninja dog could, that did not mean he could recognize any scent immediately.

"He was definitely here, and he was in a fight too. I can smell blood. It's pretty faint. It's at least a week old," Kiba said after a few minutes. "He walked across the bridge."

"Follow me," Kakashi said with mixed feelings coming to the surface. He was not sure what to feel about finding Naruto, especially after what the boy had gone through. "I think I know where his scent will be the strongest."

With that, Kakashi led them across the bridge.

* * *

Eventually, they reached the house that belonged to Tazuna and Tsunami.

Upon reaching the house, Kiba said, "His scent's pretty fresh. He was here a day or two ago at most."

"Does his scent go in that direction?" Kakashi asked, pointing in the direction of the forest where he had trained his team to climb trees with chakra.

"Yeah, it goes there," Kiba replied. He then pointed away from that direction. "It also goes there."

"I'll follow the first one. You guys handle the second one. I'll meet up with you there," Kakashi said, biting his thumb and summoning Pakkun immediately. "Pakkun, follow Naruto's scent that way," he said, pointing towards the forest.

"Sure thing," the ninja dog said as he took off running with Kakashi following him.

The pair did not have to travel long though.

As they reached the clearing in the forest, Kakashi frowned. He immediately saw fragments of rubber balls on the ground.

_It looks as though a couple of them exploded. Could he be trying to do the Rasengan training again? Lord Jiraiya did say that he could only use it with the aid of a shadow clone, so maybe he's trying to figure out how to do it with one hand._

Shaking his head, he asked, "Where'd he go from here?"

"He went a girl in that direction," Pakkun said, looking away from the path that they had just come from.

"He went there with a girl?" Kakashi asked in surprise. _Is he travelling with someone? And why would he head towards Zabuza and Haku's graves with a girl?_

Shaking his head, he rushed towards the graves.

Upon arriving, his eyes widened.

Zabuza Momochi's sword was gone.

_Shit, this can't be a coincidence._ Looking back to Pakkun, he asked, "Where'd he go from here?"

"He disappeared here," the dog said in confusion. "His friend headed away from here, but he just disappeared."

"Shadow clones leave real scents," Kakashi said with a sigh. "I think I understand the situation now. You can go. I'm going to speak with some old acquaintances and then meet up with my team."

"Right," Pakkun said. "I hope you find him. With that Akatsuki group you were telling us about around, he's in danger."

Kakashi nodded his head as Pakkun disappeared.

* * *

Kakashi immediately saw Kurenai and her team as he neared the docks. He knew what they were going to say even before they saw that he was coming their way.

The moment that he had seen that Zabuza's sword was missing, Kakashi had suspected that Naruto had headed to the Land of Water from there. If he was truly on the run, the wealth that the Mizukage would give him in exchange for the sword would be very useful.

His suspicions had been proved true when he had spoken with Tazuna. Apparently Naruto had stayed with them for over a week and had killed some bandits for the townspeople. And then, he had told them that he had some business to attend to and would visit them again later on down the road.

He had also told them that he was on the run from the Hidden Leaf Village.

_And that's not even the kicker._ Kakashi inwardly sighed at that point. Apparently, Naruto had told them to tell absolutely everything to anyone who came by looking for him.

In short, the bridge builder had known absolutely nothing about Naruto's plans.

"He's scent ends here," Kiba said, turning to face Kakashi.

"I found out where he is," Kakashi said, nodding his head. "He's probably on a boat right now. His destination is the Land of Water. As it is, there is no way that we'll be able to catch up to him before he arrives."

"If we can come here looking for him, can't we-" Kiba began.

"If we walked into the Land of Water looking for someone who isn't even a shinobi of our village, then the Mizukage might declare war on us. We're still not at full power. While they're probably not either, a war would be disastrous," Kakashi answered. "No, we need to return to the Hidden Leaf Village and inform Lady Hokage that our mission was a failure. She will probably request that Naruto be detained and returned to our village for a sum of money if he shows up, but that's all that we can do."

Kiba and Hinata looked very disappointed at that news while Shino looked as stoic as ever.

Just as quickly as the team of shinobi entered the Land of Waves, they left the country.

* * *

Two days later and many miles away, Naruto and Tayuya were walking out along the road in the heart of the Land of Water.

The pair had been in the country for a day thus far, and they had often found themselves shivering because of the temperature.

It was still fall, but in the middle of October, the Land of Water was far colder than it was in the Land of Fire. The ever present mist in the air seemed to only add on to it.

"What day is it?" Naruto suddenly asked.

Tayuya looked at him strangely before she answered the question. "It's October fifteenth, shithead."

"Huh, I didn't even realize it had already passed," Naruto said, shaking his head.

"What passed?" she asked, frowning.

"Just my birthday," Naruto replied. "It's not important or anything. It never was. No one celebrates your birthday when it's the anniversary of a tragedy."

"I wouldn't know about celebrating birthdays either," Tayuya said dryly. "Don't forget who my faggot of a boss was."

Naruto chuckled, causing him to suddenly duck as Tayuya tried to punch him in the side of his head. "I'm just laughing because most people don't talk about one of the Sannin like that."

"Well get used to it, shithead. I hear that one of the others is a gambler and the other one is a pervert," she said, almost as if she was challenging him.

"She's a drunk, and I don't think you should call her a gambler. It's kind of insulting to other gamblers. If she were to bet that the sky is blue, it would probably turn red. They call her the Legendary Sucker," Naruto said, shaking his head. His eyes glanced down to the necklace he still wore momentarily. "And the other one… he's not a pervert. He's a super pervert and cares more about peeping on girls in the hot springs than anything else. He also writes this trashy series of books that my sensei liked to read."

"And you chastise me for talking that way about one of the Sannin," Tayuya said, rolling her eyes.

"I think strong ninja have to be fucked up or something," Naruto said, ignoring her. "My sensei reads trashy books in public and giggles every now and then. His self-proclaimed eternal rival wears a green leotard and talks about _the Flames of Youth_ all day. Hell, even the Third Hokage was an old pervert."

Tayuya had started to laugh at the first couple parts, but she grew quiet when he mentioned the Third Hokage. Her voice was barely in a whisper as she asked, "Were you close to him?"

"The Third Hokage?" Naruto asked. He saw her nod her head immediately. "He was kind of like a grandfather to me. He couldn't spend too much time with me because he was the Hokage, but he was the closest thing to family I ever had."

"I'm sorry," Tayuya said quietly, stopping in place. "I can't go on being your partner unless I tell you the truth. When the Third Hokage fought _him_ during the invasion, a barrier was placed around them to prevent anyone from interfering. That barrier was set up by the Sound Four. It is partially my fault that he died. If I had not held up my part of the barrier-"

"Don't be stupid," Naruto said, looking at her intently. "I know how strong Orochimaru was. I saw him fight his former teammates at the same time, and his arms were crippled. The Old Man was the only one who could have fought him. If anyone had interfered, they would have died. I've seen a fight between two ninja that were way out of my league. One wrong move will get you caught in the crossfire. Besides, I heard that the Third Hokage used a jutsu that took his life in order to seal away the souls of the First Hokage, the Second Hokage, and Orochimaru's arms. Unless you made him use the jutsu, I don't see how it's your fault."

With that, Naruto began to walk forward, leaving Tayuya where she was standing. "Are you coming or not?"

She immediately followed after him with a frown on her face. "You know, if you're not going to take advantage of the one time I'm feeling guilty and am being nice, you can't complain when I'm a bitch."

"Maybe I'm just used to have a bitch for a partner," Naruto countered, his pink haired teammate flashing to mind for a moment.

"You've got stones," Tayuya said, laughing. "I made fatass wet his pants last time he called me a bitch."

"Or maybe he just didn't feel like rolling to the bathroom," Naruto said with a small grin.

That only caused Tayuya to laugh even more. "You know, I might have to stop calling you shithead. You're a pretty funny guy."

The lack of sarcasm in her voice threw Naruto off, but he merely changed the subject. "So what do you know about the Hidden Mist Village? I can't say I know much about it."

Tayuya cleared her throat. "Okay, I know quite a bit about it. It's arguably the weakest of the five major villages. Last I heard, they were in the middle of a civil war, though it's apparent from the look of things that the war has ended. Since the war is over with, I'm not sure who the Mizukage is, but it was some guy named Yagura last I heard. He was the jinchuriki of the Three-Tails. That means that he had the three-tails sealed inside of him."

Naruto mentally took note of that term.

"From the detailed story of your mission to the Land of Waves that you told me about on the boat, I'll skip the part about tracker ninja and go straight on to the important stuff," she said. "The Hidden Mist Village has been an isolationist village ever since the Second Mizukage and the Second Tsuchikage fought each other to the death. Despite that, they have the bloodiest past of any village. The land has been war torn from civil wars and the Bloodline Purge. As you heard from the Demon of the Mist himself, the village had a pretty bad graduation exam not too long ago. So to keep it simply, try not to bring up their past. I'm not the most diplomatic person around, but even I know that it will only cause us trouble."

"I'll keep that in mind," Naruto said nervously.

"Oh, and be careful if you talk about your past fights while we're here. That Haku guy you told me about sounds like he's a member of the Yuki clan. They're the only clan I've ever heard with that could use ice style ninjutsu. And Kimimaro, my old teammate, was a member of the Kaguya clan. They were a bloodthirsty clan from the village. Even if neither clan is well liked, mentioning that you've fought members of both clans might be a bad idea," Tayuya added. "So to recap: avoid talking about their past, avoid talking about the battles you've fought, and don't say anything disrespectful about any their Mizukage or the Seven Ninja Swordsmen of the Mist."

"If you're done, we're here," Naruto said as he walked up to the spot where the road suddenly turned off to the right. It was like they were standing on a cliff that gave them the perfect few of the mist covered village.

"It's impressive," Tayuya said, looking at the village. It was so obscured by mist that she could not estimate its size.

"I think so too."

Naruto and Tayuya suddenly turned around as they heard a new voice.

Standing before them was a middle-aged man with blue hair and a patch over his right eye. He was wearing striped pants and a striped shirt under a green robe.

"This place has the best view of the village. The mist continually moves, so you could actually get a perfect view of every building if you waited long enough. It's also why someone is always monitoring this spot," the man said. "So now, I want you to answer a question. What are you kids doing here?"

"We need to see the Mizukage," Tayuya answered.

"So you're on an assassination mission?" he asked. "Lady Mizukage would melt the flesh from your bones before you even got close to her."

"No," Naruto intervened. "We're here because we have something the Mizukage wants."

"I seriously doubt that," the Mist ninja said, looking at Naruto.

"Your hair kind of looks like fish face's," Naruto suddenly said. "I think his name was Kisame."

Tayuya shot him a glare for ignoring the bit about not disrespecting members of the Seven Ninja Swordsmen.

Surprise was clear in the man's visible eye. "You've met Kisame Hoshigaki, the Monster of the Hidden Mist?"

"Sure, he was with Itachi Uchiha at the time," Naruto said with a nod. "I've also met Zabuza Momochi, a kid named Haku, and the Demon Brothers."

"Are you Naruto Uzumaki?" the man asked carefully.

"You know my name?" Naruto asked in surprise.

"I am told that a boy with spiky blond hair was part of the team that killed Zabuza Momochi and Haku," he replied. "Given that the team composed of two teen boys and you do not look like an Uchiha, you must be the Uzumaki."

"Well, that's my name," Naruto said. "So would your Mizukage be interested in Zabuza's sword?"

The man's visible eye widened. "You brought his sword with you?"

"Yeah, it's a bitch to carry, so I sealed it up," Tayuya answered.

"And who are you?" he asked, looking at Tayuya.

"She's just my partner," Naruto said, sending a glare at Tayuya that surprised her. She seemed to understand what he was getting at though. They needed to keep her identity hidden for now.

"Very well then," he said. "Remove the scroll containing the sword and hand it to me. Until you are dismissed from Lady Mizukage's presence, do not touch your shuriken holsters or hip pouches. The civil war ended half a year ago, but everyone is still tense."

Tayuya removed the scroll and handed it to Naruto.

"Follow me."

* * *

Within an hour, Naruto and Tayuya were seated across the desk from a slender woman in her early thirties with ankle-length auburn hair and light green eyes. She had on a long sleeve blue dress that fell just below her knees.

Though Tsunade was considered a very beautiful woman by many, Naruto mentally noted that the woman across the desk from him made her look average.

His eyes moved to the men that stood in the corners of the room behind the Mizukage's desk.

To his left was the one-eyed Mist ninja that had met them outside of the village.

To his right was a man in his early twenties with short blue hair. He wore square glasses, what appeared to be headphones over his ears, a blue striped shirt, the camouflage patterned pants that only Mist ninja wore, and some kind of holster that covered his chest and upper back. The front of the holster had the plate of a forehead protector attached to it, while the back held a large sword that was wrapped in bandages with two handles protruding over his shoulder.

"I am told that you are one of the Leaf ninja who fought against Zabuza Momochi and his apprentice, Haku," the Mizukage said.

"Kind of," Naruto said sheepishly. "My status as a Leaf shinobi was revoked after a failed mission, but I did fight Zabuza Momochi and Haku when I was still part of Team Seven."

"Is he telling the truth, Ao?" she asked.

"Yes Lady Mizukage," the one-eyed Mist ninja replied. "It's unusual, but he's clearly telling the truth."

"He reminds me of my old sensei," Naruto suddenly said. "He had one eye covered too, but he didn't have a bad eye. Actually, he had a Sharingan underneath it."

"You're perceptive," the Mizukage said with a smile. "Ao has two eyes as well. Just rest assured that he can see through you."

"Last time I heard that, I was fighting a Hyuga," Naruto remarked dryly. He saw the man stiffen slightly. "So he has a Byakugan. That's pretty cool."

"I trust that you won't tell, will you?" the Mizukage asked with a hint of humor in her tone.

"Of course not," Naruto said nervously. He could tell that the woman before him could kill him in the blink of an eye if she wanted to.

"Not that I don't enjoy getting away from paperwork, but could you please show me what you have for me?" she asked.

Naruto nodded and placed the scroll on the desk before he unrolled it. He placed his hand on the center of the scroll, and Zabuza's sword appeared in all its glory.

In the right corner of the room, the Mist ninja with the sword on his back looked shocked at the sight before him.

"A sword with many names… Kubikiribocho, the Decapitating Carving Knife, the Executioner's Blade, the Guillotine Blade, and the Seversword… I had not expected to see this sword again since Zabuza's defection," the Mizukage said quietly. "The sword you have brought before me is a national treasure to my village. Unfortunately, national treasures are always either priceless or worth more money than a nation had. In this case, it is the latter."

Naruto and Tayuya both looked shocked to hear that.

"The Hidden Mist Village has not been out of its recent civil war for long. Our economy is still recovering, and this prevents me from paying you what this sword is worth," the Mizukage said with a frown.

"How much is it worth?" Naruto asked, remembering that Tayuya said that it was worth at least ten million ryo.

"It's worth fifty million ryo," the Mizukage said, shocking him. "It's a hefty amount, but it is a national treasure and it can repair itself with the blood of its victims."

"We don't need all the money up front," Tayuya suddenly said.

The Mizukage smiled at that. "That's a nice sentiment, but even paying half that amount now would be difficult."

"Could you do ten million ryo now and forty million ryo in two years?" Naruto asked, surprising everyone.

The Mizukage was quite for several minutes as she considered that. "I believe I can make that work. I might have to use my clan's funds to pay for it, but it will benefit in the long run. After all, if I don't get it now, you'll probably just sell it to the Hidden Cloud Village. They just love swords of all kinds, after all."

Naruto could not help but grin at that.

"Tell me, do you know where the remains of Zabuza Momochi and Haku of the Yuki clan are?" Ao suddenly asked, drawing everyone's attention to him.

"Sure, we buried him with his sword next to his grave," Naruto said. "Why do you want to know?"

"Naruto Uzumaki, Ao is a tracker ninja. He personally hunts down rogue shinobi and disposes of their remains. A buried body could give away many of our secrets. I would be willing to add on ten million ryo to what I'll pay you in two years if you'd give Ao directions to the location of their bodies," the Mizukage said.

"No amount of ryo will make me give it up," Naruto said, surprising everyone in the room. None was more surprised than Tayuya. "I have a price, but it's not ryo."

The second part surprised everyone even more.

"Name it," the Mizukage said carefully.

"My partner and I are to be partners as freelance shinobi," Naruto explained. "However, we don't have that many jutsu, and we need to get stronger. Since I can't ask you to train us or anything, I'd like to ask that you give us some jutsu. I'm not asking for some A-rank jutsu, or even jutsu that only your village has. We just need more jutsu period."

Tayuya allowed a smile to show on her face at that, and so did the Mizukage.

"I will allow you and your friend to each pick one of three elements. The only elements you can pick are fire, earth, or water. I will give you five jutsu for both elements that you pick from my personal library in exchange for the directions. However, you can only get the jutsu after Ao has verified that you told the truth," the Mizukage explained.

"I want fire," Tayuya said immediately.

"I want water then," Naruto said. He had actually planned on saying fire, but Tayuya had beaten him to the punch. He could see water jutsu being useful regardless though.

"I'll pick them out today," the Mizukage said. "Now, I want you two to stay in here with Ao and Chojuro while I put this sword in a safe place and get your money. After I get back and Ao knows where the bodies are located, you two may leave my office. I ask that you do not leave the village until Ao comes back though."

With that, she left and Naruto began to give Ao detailed instructions with occasional help from Tayuya.

* * *

Author's Note: And that's a wrap.

To be honest, I had intended for Tayuya to choose earth jutsu, but I thought that she would be more likely to pick fire. Unfortunately, I'm still unsure what her fifth fire jutsu will be. I have four picked out already.

Anyways, that's about it. I hope no one thought Zabuza's sword was priced unrealistically. It is a national treasure though, and it will never need repairs.

Thanks for reading and reviewing.

Next chapter, we have a long awaited event: Jiraiya's debut in the story.


	7. An Unexpected Visitor

Disclaimer: I do not own Naruto.

* * *

**The Land of Water Arc**

**7. Unexpected Visit**

"Lady Mizukage, why did you agree to pay full price?" Ao asked once he was alone with the woman in question. "You could have threatened them or told them that you'd keep their presence a secret only if they gave you the sword."

The Mizukage shook her head in response. "Don't be like that, Ao. We are not the Bloody Mist Village any longer. Just because we can do something, that doesn't mean that we should. Naruto Uzumaki and his companion came here with something that will stand as a symbol of hope to our village. I would not dare tarnish such a symbol by obtaining it through treachery."

Ao nodded his head, not surprised. "Perhaps your decision was wiser than what I would have done. After all, he is a jinchuriki."

"And the lack of a seal master in our village would have made dealing with him nearly impossible," she added.

"But what of the Hokage's offer to capture him and turn him over to her forces? It would get us out of paying the rest of what we owe to him, and it would get us much needed money," Ao interjected.

The Mizukage sighed as she removed the letter that she had received from the Hokage earlier that day from her desk. "I can't deny that turning him in for twenty-five million ryo is appealing, but that wouldn't end our debt to him. His partner has no such bounty that we are aware of, so we would still have to pay her. Besides, I'm willing to take a gamble on this kid. He met Zabuza Momochi and Kisame Hoshigaki, and he has already sold us one sword. If we can get him to look for the other swords, our village would benefit greatly."

"His wallet would too," Ao said pessimistically.

"It would," she agreed. "You're also ignoring one important fact. If those two do not live long enough to collect what we owe them, we don't have to pay. However, if they do live long enough to collect what we owe them, despite their decision to become freelance shinobi, then they will either be very lucky or very strong. Either way, being on their good side could be advantageous."

Ao nodded his head, seeing that he would not win.

"After I write a letter, informing the Hokage that I have only vaguely heard of Naruto Uzumaki and that I'll inform her if he comes around, I want you to have the letter sent to the Hokage before you depart. I know that you wish to reach the Land of Waves as soon as possible, but this comes first."

"Yes Lady Mizukage," Ao said respectfully.

He turned to the door and suddenly felt his eyes go wide.

"Lady Mizukage, it appears we have an uninvited guest in the village," he said, turning back to face her.

"I'll be standing by," she replied casually as she wrote her letter. "If he attempts to capture our guests, I will deal with him."

Ao actually looked surprised at that. "You know who he is?"

"He's not uninvited," she replied. "He informed me that his former apprentice was headed in this direction two days ago. Once I learned of Naruto's situation, I asked Chojuro to tail him. Even Jiraiya of the Sannin will not risk fighting one of the Seven Swordsmen in the middle of the Hidden Mist Village."

As she finished writing the note, her thoughts turned sour. In all honesty, she knew that she could not defeat Jiraiya if she had to fight him. She was quite possibly one of the fifteen strongest ninja in the world in her opinion, and she had a tendency to underestimate her strength. Jiraiya was quite possibly one of the five strongest ninja in the world though. Even with an army of shinobi at her side, she did not believe that a fight between her and the Toad Sage would not end in her favor.

She quickly folded the letter, slipped it inside an envelope, stamped it shut, and handed it over to Ao.

"I'll be back within a week," Ao said as he departed.

With that, the Mizukage headed to the roof of the building to look over the village and think.

* * *

"Wow," Naruto said as he stood in the doorway of the Misty Shuriken shop. It was an all-in-one ninja shop that carried clothes, supplies, and ninja tools. As if seeing everything he could need at one time was not enough, it was quite easily the largest shop that Naruto had ever been inside.

"If you keep looking around like an idiot, you're going to be a shithead again," Tayuya said quietly, not wanting to attract attention. "Now, go and look around. And if I catch you getting kill-me-orange clothes like you were wearing when we first met, I'm going to show you just how proficient I am with genjutsu."

"Says the girl who doesn't have her flute anymore," Naruto said, thankful that all her genjutsu techniques were sound based.

"Dipshit, look over there," Tayuya said, pointing off to one of the corners of the room.

Naruto groaned when he saw that they actually carried flutes in the shop. "Fine, I won't get any orange."

"Damn straight you won't," Tayuya said as she walked off.

_Okay, so I somehow wound up with a girl that is the epitome of everything Shikamaru said he didn't want in a wife. Still, she's kind of cute, even if she has the foulest mouth in the Elemental Nations and would probably castrate me if I admitted that she was cute._

Shaking his head, Naruto made his way to the part of the room where the teens' clothing was located at.

_If I can't have any orange, I guess I'm going to go with all black. It'll be a change, but it might be for the best._

Knowing that he would not be seeing another clothing store for a while after they left the village, he picked up three pairs of black sandals, five pairs of black pants, five solid black shirts with long sleeves, three pairs of fingerless black gloves with metal plates on the back of them, some bandages, a few shuriken holsters, a few kunai holsters, and a few hip pouches.

With his arms full, he walked up to the counter and set it all down.

The cashier was a girl no more than four years older than him. She smiled and asked, "You must be going on a journey. We never have anyone pick up so much stuff."

Naruto laughed as he scratched the back of his head sheepishly. "I'm actually not done yet. That's just the clothes that I wanted. I still need some kunai, shuriken, fuma shuriken, scrolls, makibishi spikes, food pills, and paper bombs."

The girl went wide-eyed at that. "How much do you want?"

He looked thoughtful for a moment. "I'll take two hundred kunai, two hundred shuriken, ten fuma shuriken, twenty-five scrolls, twenty-five pounds of makibishi spikes, ten pounds of food pills, and five hundred paper bombs."

The cashier's mind was really blown away by the sheer volume of what he had asked for.

Fortunately, the shop had more than enough for that.

"I'll ring you up then," the cashier said nervously. "The sandals will cost six hundred ryo, the pants will cost fifteen hundred ryo, the shirts will cost a thousand ryo, the gloves will cost six hundred ryo, all the bandages will cost five hundred ryo, the shuriken holsters will cost six hundred ryo, the kunai holsters will cost six hundred ryo, the hip pouches will cost a thousand ryo, the kunai will cost ten thousand ryo, the shurikens will cost two thousand ryo, the fuma shuriken will cost five thousand ryo, the scrolls will cost five hundred ryo, the makibishi spikes will cost twenty-five hundred ryo, the food pills will cost ten thousand ryo, and the paper bombs will also cost ten thousand ryo. That brings the total up to forty-six thousand, three hundred ryo."

It was almost as though she expected him to say that he did not have enough, by the look on her face.

Instead, Naruto handed her five paper bills. Each one was ten thousand ryo.

"I hope you can make change," Naruto said with a smile.

"Looks like you know what you're doing," Tayuya said, approaching him from behind. She had a stack of clothes in her hands too. "You better have plenty after he gets his order. I'll be getting the same shit."

The cashier actually groaned when she heard that. "It'll almost clear out our inventory for everything you're buying, but we have it."

"That's good to hear. She gets pissed when people disappoint her," Naruto said in a whisper as he took his change from the girl. "They say the last person to disappoint her eat a cactus whole after she was done with him."

Though it was said in a whisper, Tayuya heard every word of it and smirked in response.

The whole think was bullshit that Naruto had made up on the spot, but it was the type of thing that could have been true for all he knew.

"I'll get both of your supplies after your friend pays," she said nervously.

With that, Tayuya placed her clothes on the counter. Like Naruto, she had picked up three pairs of black sandals, five pairs of clothes, some bandages, a few shuriken holsters, a few kunai holsters, and a few hip pouches. Unlike him, her clothes were a little different and she had something else in the pile.

Tayuya had picked an all black attire, just like Naruto. However, it was composed of black pants, a short sleeve black shirt, and black wristbands like she had worn since Naruto met her. In addition to that, she had picked up a flute that was solid white.

Upon seeing the pearl white flute, Naruto was captivated.

"I don't think you have enough to make this purchase," the cashier nervously said. "That flute was carved from a pearl that came directly from the Second Mizukage's clam summon. It should not have even been out of a display case. It's our most valuable item here."

"How much is it?" Tayuya asked, her stare making the cashier even more nervously.

"It's half a million ryo," she answered.

"Okay," Tayuya said, counting out five hundred fifty thousand ryo and handing it to the cashier. "That should be enough for everything, right?"

The cashier fainted at that point.

"What's so special about that flute?" Naruto asked, looking at Tayuya.

"The Second Mizukage was supposed to be one of the greatest genjutsu users in history. If this flute is really carved from the pearl of his summon, it's probably the best flute I'll ever find. It might even make my genjutsu stronger," Tayuya explained.

"I see," Naruto said, only slightly understanding what she was talking about. "Maybe we should get some scrolls ready to seal everything up."

"That's not a bad idea blondie," Tayuya said. "Get your scrolls out, and I'll draw the seals on them. I'll use more advanced seals this time. There will be one seal for every type of item we bought."

So while they waited for the cashier to wake up, Tayuya took Naruto's four blank scrolls went to work. First, she drew out seals for each piece of their new clothes on two scrolls, one for each of them. Then, she made the seals for each piece of ninja equipment that they were in the process of getting.

Once they finished, Tayuya sighed. "The cashier is still out."

"Forget her," Naruto said, turning to face the door. "Someone's coming."

Tayuya looked at him strangely, only turning to see what he was looking at after a few moments.

She looked at the door to the shop just in time to see a man that she immediately recognized on sight: Orochimaru's most hated enemy, Jiraiya of the Sannin.

"It's been a while, Naruto," Jiraiya said as he approached them.

"What are you doing here, Jiraiya," Naruto said, forcing himself to use the man's name. No hostility was in his voice, but he was mentally preparing himself for the fight that he expected.

"I haven't been back to the village yet," Jiraiya said casually. "The Old Man had no way of contacting me, and neither does Tsunade. It kind of makes things easy. If they can't contact me, then they can't give me orders. In fact, I only know of what happened to you because the entire Inuzuka clan was looking for you not too long ago. My summons overheard a discussion between two of their members and reported straight to me."

"How'd you know I'd come here?" Naruto asked.

"My summons informed me that you were getting passage to the Land of Water by boat. By coincidence, I was already here, checking to see the current status of the village," Jiraiya said, shaking his head. "But anyways, I'm not here for any of that. I want to talk to you as master and apprentice once more before I return to the village. Your friend can handle things here."

"Why should I let you take him anywhere?" Tayuya asked defensively.

"Your resemblance to the only kunoichi of Orochimaru's Sound Four is uncanny," Jiraiya suddenly said. "I'd rather dismiss it as a coincidence and not do any digging on you. I don't have any interest in finding out about you. Just let me speak with Naruto in private, and I'll leave in peace."

Though Tayuya looked furious, Naruto nodded his head. "Tayuya, I'd appreciate it if you sealed up our stuff after that girl wakes up. Maybe get us a couple rooms at one of the hotels after that, and we should meet up at dinner time. I saw a ramen stand that looked promising."

"Don't do anything stupid, shithead," Tayuya said, earning a small frown from her partner.

"I won't," Naruto promised. "Pervy Sage, let's go."

Jiraiya nodded, leading Naruto away from there.

* * *

A couple hours later, Naruto was walking down the street in the Hidden Mist Village alone.

His conversation with Jiraiya had changed things a great deal.

Of course, the biggest change for Naruto had been reverse summoning. He had been summoned to Mount Myoboku, the home of the toads, the instant that he was outside of the shop.

He had talked with Jiraiya on the mountain, and he had learned two very important facts. One was that Jiraiya was on his side and agreed with his actions. The second was that he needed to stay out of the hands of Tsunade's men at any cost.

It had surprised him to hear Jiraiya say that, but it had made a little more sense when he had learned that if he returned to the village, he would most likely never be allowed to become a ninja again.

He frowned as he remembered the worst news that Jiraiya had given him: they could not meet with each other again after that point. Jiraiya was still a loyal Leaf ninja, so he would have to listen to the orders of his Hokage.

_At least he did what he could. What's the odds that we could make such a good deal with the toads before we really had to be on different sides?_

Jiraiya had offered Fukasaku and Shima, the elder toads, a proposition. Because Naruto and Jiraiya would be opposed at times in the future, neither one of them should be allowed to use toads against the other. As such, neither one of them could ask the toads to reverse summon the other anywhere, and they could not summon toads to fight each other.

Naruto had wished that the conversation had lasted longer, but Jiraiya had revealed that only Mount Myoboku was safe for their conversation, which put him in a rough spot with the Mizukage. If she thought that Jiraiya had kidnapped him, she could ban him from entering the country.

Still, Naruto had gotten something in the end that made the conversation truly worth it. Jiraiya had given him a book on fuinjutsu, which he claimed ran in Naruto's blood.

Naruto was broken from his thoughts as he was slammed against the wall of a nearby building.

"Where in the fuck did you go?" Tayuya demanded as she held him against the wall. "Some shithead of a sensor showed up, asking where you disappeared to. No one could find you. So what in the fuck is going on?"

"Pervy Sage wanted to talk to me, so he had me reverse summoned to the home of the toads," Naruto answered.

"You can summon?" Tayuya asked, clearly surprised.

"I was his apprentice. He taught me to summon and use the Rasengan," Naruto answered, not all that happy by the fact that she was still holding him against the wall.

"None of this shit adds up," she said angrily. "You're supposed to be some shithead who was at the bottom of your class. Instead, you became a fucking hero in a minor country and were the god damned apprentice of the biggest fucking pervert in the world. What aren't you fucking telling me?"

_She's pissed. She's cussing even more than normal._

Sighing, Naruto looked her in the eyes. "I'm the jinchuriki of the Nine-Tailed Demon Fox. I guess you could say that everything I am is because of that."

Tayuya released him at hearing those words. "You're a jinchuriki?" she asked, honest shock in her eyes.

"Yeah, and I'll understand if you don't want to be my partner anymore," he said quietly as he turned and began to walk away.

In an instant, he was turned around and she punched him in the face with enough force to send him across the street.

"Don't keep anymore secrets from me, shithead," she said, shooting a weak glare at him. "Now get your pansy ass up so we can get something to eat. You're buying."

"Right," Naruto said sheepishly as he stood up. Though he looked almost embarrassed at that moment, his true feelings were completely different. He felt happier than he had ever been at the realization that she did not care about his burden.

For the first time in a long time, Naruto felt content.

* * *

Author's Note: And there's Chapter 7. Personally, I was not happy with Jiraiya's part in the chapter at all. I had initially planned on showing everything, but the scene was not coming to me.

Still, I think the chapter came out fairly well.

As a word of warning, I'll be taking a break from fanfiction for 1-2 weeks after I finish The Land of Water Arc in Naruto: A New Destiny and The Chunin Exams Arc in Secrets.

I need to work on The Shadows of Caldreth badly. I can't put it off any longer. I have been putting fanfiction above original fiction, so I need to rectify it. It shouldn't take me anymore than two weeks to get The Shadows of Caldreth on track to the extent that I can start updating this and Secrets again without getting behind schedule of my book.

So again, there will be one more chapter of Naruto: A New Destiny and two more chapters of Secrets before I take this 1-2 week break.

I hope everyone understands. After all, I actually get paid for my original fiction while fanfiction is just a hobby.


	8. On the Move Again

Disclaimer: I do not own Naruto.

* * *

**The Land of Water Arc**

**8. On the Move Again**

Five days had passed since Naruto and Tayuya had arrived in the Hidden Mist Village, and the pair was sitting in the former's hotel room. Though they had separate rooms, it seemed that Tayuya was not actually fond of being alone.

As such, the pair had spent a great deal of time together, mostly telling stories. When they were not telling stories, Tayuya played her flute and Naruto read the extensive book of fuinjutsu that Jiraiya had given him.

Naruto smiled fondly at the thoughts of the stories that he had shared. For the first time, he had told someone the truth of the Mizuki Incident, the whole story of the mission to the Land of Waves, and everything that had happened during the Chunin Exams and the following invasion.

It was relieving to have someone who would listen to the stories without judgment. Tayuya never had mixed feelings about what he held within him. In fact, the only hint that he had even gotten that she had feelings on the matter at all was that she seemed to respect him more for the burden he had carried.

"So what's the plan after this?" Tayuya suddenly asked, making Naruto realize that she had stopped playing her flute. The melody she had a tendency to play was soothing and helped him absorb what he read more easily, so it surprised him that he had not noticed its absence. "Where should we go once we're done here?"

"We need to find somewhere to train where no one can find us," Naruto said after a few moments. "We're going to some new jutsu soon, plus you said you know how to create genjutsu and I have this book on seals. If we spend a couple months away from everyone, we could get stronger."

Tayuya nodded thoughtfully. "There's an island south-east of the Land of Hot Water and north-east of the former Land of Whirlpools. It's an unclaimed island without any civilization on it from everything I've heard about it."

Naruto smiled. It seemed that Orochimaru had made the Sound Four do extensive research on every landmass and country in the Elemental Nations a while back. From what he could see, it could only benefit them now.

"That sounds like a good place to train, but getting there might be hard," Naruto said.

"We can take a boat to the east border of the Land of Fire and jump overboard when we come close to the island," Tayuya said with a shrug as she looked at her partner. He was sitting in front of the coffee table in the living room with his book sitting on it while she was at the kitchen table.

"That sounds like a plan," Naruto said.

A knock suddenly came at the door, and it was followed by a muffled voice that they could barely understand.

"Ao has returned. Lady Mizukage will see you now."

Exchanging a look, the partners rose to their feet and began to move towards the door.

* * *

Upon entering the Mizukage's office, Naruto noticed that the woman before them was smiling.

"Naruto Uzumaki, I'd like to thank you for everything you have done," she said with a smile. "Thanks to you, we have located the bodies of Zabuza Momochi and Haku Yuki. You'll be pleased to know that their ashes were laid to rest where your team buried their bodies as well."

"Thank you, Lady Mizukage," Naruto said politely. He was glad that their remains were left where they were buried. He had grown to respect both shinobi in his short time of knowing them.

"Think nothing of it," she said. "All that remains is to give you the jutsu I owe you."

With that, she set a wooden chest on her desk. It was roughly the size of a breadbox.

She opened it, revealing that there were ten scrolls inside of it.

"For you, I put in scrolls for the Water Clone Jutsu, the Water Prison Jutsu, Water Style: Raging Waves, Water Style: Liquid Bullet, and Water Style: Waterfall Basin Jutsu," she said, looking at Naruto. She then looked at Tayuya. "And for you, I put in scrolls for Fire Style: Fireball Jutsu, Fire Style: Phoenix Flower Jutsu, Fire Style: Phoenix Nails Jutsu, Fire Style: Dragon Flame Jutsu, and Fire Style: Misty Flames Jutsu."

"How did you get so many fire jutsu that are specific to the Uchiha clan of the Hidden Leaf Village?" Tayuya asked in surprise. The first three jutsu were created by the Uchiha clan, after all.

"I don't know," the Mizukage replied honestly. "Though these jutsu are from my personal collection, I learned the first few fire jutsu from my predecessor's library. He had those jutsu in there, and he was dead by the time I found out about it. It's not as if I can simply ask him about it."

"It doesn't matter anyways," Naruto said. "Thank you for this."

"No, this was a small price to pay," she said. "Consider yourselves friends of the Hidden Mist Village, and make sure to bring back any of the rest of the Seven Swords that you find. I'd be willing to pay fifty million for any of the others, except for Kisame Hoshigaki's sword. It's worth more than any of the others."

"We'll be back," Naruto promised as he picked up the chest. "Oh, and I wanted to give you a heads up. Your village isn't the only one with the Hidden Mist Jutsu anymore. Kakashi-sensei saw Zabuza use it with his Sharingan."

The Mizukage frowned at that. "Thank you for the information. Hopefully, he has not shared it with anyone else. It's a jutsu that we've been careful to keep from the other villages."

"That's why I wanted to tell you," Naruto said with a smile. "Good bye, Lady Mizukage."

"There's no need for such a respectful title," she said with a smile. "My name is Mei Terumi. Feel free to address me by my name."

"You're a Terumi?" Tayuya asked, startled.

"You've heard of my clan?" Mei asked pleasantly.

"Your clan is known for being able to use lava style ninjutsu," Tayuya said quietly. "My last boss always wanted to get his hands on one of your clan."

Mei smiled at that. "Only my father was a Terumi. My mother had an equally powerful, but different, kekkei genkai. Good luck, Naruto Uzumaki. I wish you the same luck, Tayuya."

Tayuya froze at that. They had been quiet around her about Tayuya's name, after all.

A single look told them that the Mizukage knew who Tayuya was.

"Good bye," they both said, leaving her office.

As soon as they were out of the office, Tayuya looked towards Naruto.

"I want to get out of here as soon as possible. Let's go to the hotel, get our stuff, and leave," she said.

"It's a good thing they consider us friends," Naruto said. He never said anything in disagreement with his partner's plans though.

* * *

As Naruto and Tayuya were getting everything read to leave the Hidden Mist Village, Tsunade was sitting in her office with a letter in her hands.

_If Naruto did not go to the Hidden Mist Village, where could he be? Maybe he went to the Hidden Cloud Village instead. But if he did, A would easily learn of the Nine-Tails inside of him and he would either forcibly recruit him or have the Nine-Tails removed so it could be sealed in someone loyal to his village. No, I have to hope that he just hasn't arrived in the Hidden Mist Village yet. Damn it! Where's Jiraiya?_

"The Mizukage's letter must have just beaten me here."

She suddenly turned and saw Jiraiya sitting in her window sill.

"I've been waiting for you," she said with a hint of annoyance in her voice.

"Are you that eager to get yelled at?" Jiraiya said with an expression on his face that she had not seen in a long time: anger. "How stupid could you be, Tsunade? You kicked Naruto out of the Shinobi Corps, and then you didn't expect him to run away?"

Tsunade looked as though she had been slapped at that.

"How could you be such a fool? Have you learned nothing since you met him? Anyone who knows Naruto knows that being Hokage meant everything to him. By kicking him out of the Shinobi Corps, you took his dream from him," Jiraiya said, shaking his head.

"He lost control and attacked Kakashi under the fox's influence," she protested.

"And that should concern me?" Jiraiya asked, looking at her as though she had said that the sky was blue. "Jinchuriki lose control. The last jinchuriki of the Eight-Tails died when he attempted to go beyond his two-tailed state, and he was in his mid-twenties. The fact that Naruto managed to go to his one-tailed state and not completely lose control to the fox is a testament to his potential."

"What are you talking about? How did he not completely lose control? He attacked Kakashi," she demanded.

"I heard you the first time," Jiraiya said. "He clearly had a lapse in control and its will influenced him a bit too much. If he actually lost control, the Nine-Tails would have completely taken over, and Kakashi would be dead. Not even I would stand a chance against the Nine-Tails."

Tsunade looked away at that point. "Regardless, my grandmother never had any trouble controlling such a low level state."

"Your grandmother was a fully trained seal master when she became a jinchuriki," Jiraiya said flatly. "I thought you were supposed to be the smart one. Mito Uzumaki could tighten the seal at will if she wanted to, essentially acting as a choke collar. Besides that, she was around Hashirama Senju almost every second of the day. The Nine-Tails was never considered to be stupid. Even if it could influence her, its chakra would be suppressed with some wood style ninjutsu, and then its jinchuriki would just tighten the seal and punish it afterwards."

Tsunade looked taken aback at that.

"You were close to your grandmother, but I was even closer to Kushina, my student's best friend, lover, and wife. Sarutobi-sensei let me go over the notes that the First Hokage and his wife had compiled over the years, so I know even more on this matter than you do," Jiraiya said seriously. "Like Mito, Kushina had special abilities that would let her suppress the chakra of a tailed beast. Unlike her predecessor, however, she could do it without fuinjutsu. That was why she was chosen to be the second jinchuriki. Comparing Naruto to Mito or Kushina is idiotic. They had special abilities, and they grew up like normal kids. You overestimate the emotional stability of an average jinchuriki."

Tsunade looked shocked by everything Jiraiya had said to her thus far, but he was not quite done yet.

"Jinchuriki are not stable. They grow up hated for the burdens they carry. You read about Gaara, the son of the Fourth Kazekage, didn't you? He's about as stable as most jinchuriki are," Jiraiya said, making her wince. "Akatsuki has two tailed beasts already, the Five-Tails and the Seven-Tails. Their jinchuriki went with Akatsuki willingly. Did you know that? They didn't even put up a fight. They wanted to be free of their burdens, even at the cost of their lives. Let's not forget the jinchuriki of the Three-Tails. He started the Bloodline Purge in the Land of Water. Oh, and the jinchuriki of the Six-Tails went rogue. Finally, the jinchuriki of the Eight-Tails is said to speak in rap. Outside of the jinchuriki of the Two-Tails, Naruto is arguably the most stable jinchuriki in the world right now. Even then, he has his insecurities. Without proper training, the fox will be able to manipulate his insecurities. So you shouldn't be surprised that the Nine-Tails managed to get him to become consumed by its will for a little while. In fact, you should feel proud that he didn't go into a higher state during the whole ordeal."

"I hold Naruto to a higher standard than those others," Tsunade suddenly said. "I've seen what he's capable of. Even if he doesn't have special powers, he should still be comparable to his predecessors."

Jiraiya's hands balled into fists at those words. "You won't reverse your decision?"

"I made the right decision," she said firmly.

"Then stop looking for him. He's not your property," Jiraiya said.

"The Nine-Tails is my property. By extension, he is too," Tsunade said. "We will find him and bring him back. You're going to help too."

"No, I won't," Jiraiya said, shaking his head. "I officially retired thirteen years ago, and I'm not going to lift a finger to help you until you stop being a fool. Good-bye Tsunade. I'm going to make sure Akatsuki doesn't go after my godson."

"I'll stop you," Tsunade said, rising to her feet.

"You could stop me, but I considered this possibility," Jiraiya said, shaking his head. "I was never here."

With that, Jiraiya disappeared in a cloud of smoke.

_No! It was a shadow clone! Damn it, this isn't good. Jiraiya really did retire too. I can't send anyone after him. Besides, not even Kakashi, Guy, and Asuma would be able to bring him back if I could send someone after him._

Tsunade laid her head down in defeat.

She was well aware that she could have avoided everything by reversing her decision and letting Naruto return as a Leaf shinobi, but she could not do that. Her stubborn pride would not let her.

* * *

Author's Note: As you may have noticed, I gave Tayuya a jutsu called Fire Style: Phoenix Nails Jutsu in this chapter. It's not a jutsu of my creation. Itachi used it in his fight with Killer Bee in the manga. I use the dubbed names of jutsu quite often, and we only know the manga name of the jutsu right now. Thus, I improvised on the name. It might be closer to Phoenix Flower Shuriken or Phoenix Flower Nails when it is actually named by Viz, but I like my name for it better.

The bombshell of Jiraiya leaving the Leaf Village like I had him do should surprise many of you. It surprised me, after all. I had never planned on it happening. However, I felt that it was a reasonable reaction at Tsunade's decision. Essentially, he is playing the legacy of his student and his godson before the village that he served for thirty years as an active ninja.

I know I said I'd do a training arc after this, but I've changed my mind. That's not to say that the events of the arc won't happen, but I've decided to time-skip over it. I'm doing this because I feel that it would be better if I left a good deal of the training a mystery. So while you will know what five elemental jutsu each character learns, they will grow as shinobi in other ways.

Another fact that made me decide to do the time-skip is that there is no conflict in their training trip. Without conflict, there is no story. Chapters about training and nothing but training would simply be filler.

I hope everyone will be satisfied with this decision.

Thanks for reading and reviewing.

I will now resume work on Secrets before taking a 1-2 week break from fanfiction so I can work on The Shadows of Caldreth, the second book in my epic fantasy series.

After I return, you'll see Naruto and Tayuya's entrance into the shinobi world as freelance shinobi.


	9. Out of the Shadows

Well, I've been gone for two weeks, and here's the chapter of Naruto: A New Destiny that you guys have been waiting for. Just to give you a heads up, the time skip that occured between last chapter and this one was far greater than I planned. That was done after much deliberation though.

* * *

Disclaimer: I do not own Naruto.

* * *

**Out of the Shadows Arc**

**9. Out of the Shadows**

Two years had passed since Naruto Uzumaki's removal from the Ninja Corps of the Hidden Leaf Village.

Ever since he disappeared from the village, his name had popped up occasionally in various minor countries, and it was always said that he traveled with a fiery redheaded kunoichi, but no one knew what type of skills he possessed or the identity of his companion.

It helped that anyone who had reason to keep an eye on them was fed misinformation. No one was better equipped to inform spies of misinformation than the former Leaf shinobi, Jiraiya.

It also helped that no one, not even the Leaf Village, was aware that Jiraiya had been working with Naruto for a year and a half. His spy network had gained a new aspect to it. If anyone needed Naruto to do a job, Jiraiya would find out about it and inform Naruto. In short, none of Naruto's clients needed to know where he lived.

The newly turned blond fifteen year old boy stretched his arms out as the sun beat down on him. It had been a long two years for him, but he had no reason to complain. His companion, Tayuya, had become the greatest friend he had ever had in that time. Contrary to what Jiraiya liked to suggest, they were just that: friends.

"How long do we have to stay here, blondie?" his companion suddenly asked. "I fucking hate this place. You know that."

Naruto chuckled at her question, but he stopped when she glared at him. "I don't blame you. It's a desert after all."

"Then why did you take the fucking job in the first place?" she asked with another glare.

"Bitch all you want, but you're not the one who is having trouble getting scrolls for your affinity," Naruto said with a sigh. "You got fire jutsu right off the bat, and Pervy Sage even taught you some earth jutsu. And sure, I've got some water jutsu and some fuinjutsu, but I still don't know any wind jutsu. How fucked up is that? I can't even use my affinity yet."

"And your old buddy, the new Kazekage, is just going to give you some wind jutsu for taking down a rogue ninja?" Tayuya asked skeptically.

For the millionth time in the past two years, Naruto sighed. "You really need to start reading the files I give you before you seal them up. We're not going after just any rogue ninja. We're going after Sasori of the Red Sand, the most infamous rogue ninja in their village."

He glanced at Tayuya, not surprised that she looked shocked.

"What's wrong with you? We're not strong enough to take out an S-rank ninja. Surely you figured that out when we couldn't even take out the Legendary Stupid Brothers without that pervert of a godfather showing up," Tayuya said, a mixture of worry and anger in her eyes.

"That was a year ago," Naruto said with a frown. He hated being reminded of all the times he had gotten in over his head. "Besides, Pervy Sage is going to occupy his partner while we fight Sasori. I already figured out how we're going to beat him anyways."

"This'll be interesting to hear," Tayuya said, shaking her head.

"We need to destroy the shell of a puppet he moves around in first," Naruto said, remembering what Jiraiya had found out about Sasori. "Immediately after that, you hit him with a frontal attack while I seal off his chakra."

"Can we beat him then?" Tayuya asked skeptically. "S-rank ninja aren't just good at one thing. He can probably kick your ass with taijutsu."

"You really need to read what I give you," Naruto said with a groan. "Pervy Sage found out that he has a puppet body. Once I seal off his chakra, he won't be able to move at all. Gaara said he'd only give me some scrolls on wind jutsu if I can bring him in alive, and I'll be damned if I don't go the extra mile."

Tayuya shook her head with a smile. "Let's get this party started then."

Naruto nodded with a grin as he began to run forward, chakra flowing from his feet so that he never even sunk into the sand by an inch. He did not want sand getting into his sandals, after all.

Tayuya immediately followed Naruto. Even if she was not too confident in his plan, she would have stood by his side even if they were fighting all five Kage.

They trusted each other unconditionally.

* * *

"What in the hell is he doing here?" Deidara asked as he looked at the man before him. It was not an everyday occurrence that Jiraiya of the Sannin showed up before him.

They were supposed to be doing reconnaissance for the upcoming mission to capture the One-Tails' jinchuriki, not fighting a kage level shinobi.

"You must be after Naruto," Jiraiya said casually. "He's not even a mile behind me, after all."

Deidara and Sasori exchanged looks at that.

"That's not why we're here," Deidara said with a grin. "But I'd be more than happy to show the Nine-Tails some of my art."

"Only one of you could possible get to him while the other keeps me busy," Jiraiya said in an almost amused tone. "Puppeteers aren't too hard for me to take down, so are you sure you want to risk me beating your partner and then going after you?"

Deidara looked conflicted, but it was Sasori's words that convinced him.

"You're the faster of us," Sasori said calmly. "We couldn't outright kill him, even if we fought together. However, you can keep him busy while I capture the Nine-Tails. Then, you can escape on one of those exploding birds you call art."

"Fine," Deidara said, not willing to argue for once. "I'll consider it practice. If I can beat him, I can beat Itachi, yeah?"

Jiraiya smiled as he evaded a sudden bomb blast and Sasori made his way away from them. Sasori was arguably the weakest member of Akatsuki, so it made sense to let Naruto practice fighting him before any of the others.

* * *

Sasori came to a stop as he saw Naruto and a redheaded girl standing before him. It seemed that they had been expecting him. Still, he was not worried. S-ranked shinobi were not susceptible to such simple traps, after all.

"Fire Style: Fire Dragon's Breath," she whispered as she formed a series of hand signs. Suddenly, she exhaled a powerful blast of fire that shot out much like a pressurized blast of water would.

The sudden maneuver shocked Sasori, but he was able to do little more than open the back hatch of the puppet and jump out of it backwards before the puppet could catch fire. It would have incinerated him otherwise.

He immediately started looking around as he saw that Naruto was no longer in plain sight. It seemed he had disappeared when his partner shot fire at him.

"Uzumaki Sealing Style: Binding of the Shinobi," Naruto suddenly said, making Sasori look behind him. Much to his shock, he was standing in the symbol of the Uzumaki clan drawn on the sand. That did not shock him as much as the sudden loss of chakra did though.

Sasori fell to the ground in his puppet body. As much as he would have liked to, he was unable to even lift a finger.

"Thanks for making it easy on us," Naruto said with a grin. He looked to his teammate and nodded.

Suddenly, she shot a series of ten small fireballs into the air.

_What was that?_

As much as he would have liked to speak, such would have required him to move the mouth of his puppet body, which he could not do at the present time.

"With any luck, he'll actually manage to capture Deidara," Naruto said with a grin. "But for now, let's get puppet boy to the Hidden Sand Village. I love it when everything goes according to plan."

Sasori felt a sense of dread overcome him as he realized how foolish he had been. Because of his arrogance, he had tried to take on the jinchuriki of the Nine-Tails without learning what his abilities were first.

_I should have known something was wrong when Zetsu reported that he was no longer able to spy on the boy. Jiraiya of the Sannin must have started teaching him sealing techniques beyond anything I've seen. But wait… he used an Uzumaki technique. This isn't good. That clan was supposed to be wiped out. If he gains their knowledge, then Akatsuki might actually fail._

His thoughts were swept away as he was picked up and carried away. All thoughts of survival fell away as he realized that just being separated from the seal on the ground was not enough to free him from the seal's chakra suppression abilities.

* * *

"You actually succeeded," Gaara said without a hint of emotion in his voice.

They were in the Kazekage's office, and the puppet body of Sasori was lying on the ground between them.

"Don't sound surprised," Naruto said with a grin. "We're good at what we do. How many other organizations of shinobi can boast a one hundred percent success rate?"

"Akatsuki," Gaara deadpanned.

"I don't think so," Naruto said, pointing at Sasori.

A ghost of a smile came to Gaara's face as he nodded his head, conceding the point. "You're only two people though. It's not hard to believe that you always succeed. If I was in your position, it would be the same success rate."

"Of course," Naruto said with a smirk. "You wouldn't even need a partner. You're probably one of the ten strongest ninja in the world."

"I wouldn't go that far," Gaara said.

Naruto nodded, sighing. He hated to agree that Gaara was not one of the ten strongest around, but the only two Kage that could really qualify for being one of the ten strongest shinobi in the world were the Tsuchikage and the Raikage. Orochimaru, Itachi Uchiha, and Kisame Hoshigaki were all stronger than Gaara, and it was quite likely that there were even more powerful members of Akatsuki out there.

"So, do I get the wind jutsu?" Naruto asked impatiently.

"Yes," Gaara said with a nod as he walked over to his desk, withdrew a dozen or so scrolls from it, and handed them over to Naruto. "Good luck Naruto. You must know how risky it was doing an assignment for me."

"You'll wait until I'm gone before you send a hawk to the Hidden Leaf Village, right?" Naruto asked.

"Yes," Gaara said with a frown. "They are our allies, so I am required to at least inform them I saw you."

"That's why I left my partner outside of the village," Naruto said with a grin. "I don't want them knowing who she is yet. But anyways, don't worry about anything. We're friends, but you're the Kazekage first. Put your people first, and I'll do what I've always done."

"You're a good man," Gaara said seriously.

"And you are too," Naruto said with a smile.

"You've saved more lives in the last two years than any village," Gaara said as he crossed his arms. "I'm told that you've even done missions for the Feudal Lord of the Land of Fire."

"He asked me to take out some bandits for him last year," Naruto said with a nod. "It was the least I could do after he forced Tsunade to remove me from the Bingo Books."

"She made a grave mistake," Gaara said as he turned away from Naruto. "You're a great shinobi, and any village would be happy to have you."

"Not any village," Naruto said as he turned away from his friend. "The one village that should have been happy to have me didn't. I wonder what my father would say about it if he was here now."

"Your father?" Gaara asked, intrigued. He knew nothing of Naruto's heritage, after all.

"Yes," Naruto said as he headed to the door. "You're not the only son of a kage, after all."

With that, Naruto headed downstairs to collect his money so that he could leave.

He was eager to get out of the village. Hidden villagers were not high on his list of likes, after all.

* * *

Author's Note: I've got something I want to talk about, but first I'll say that next chapter will focus on the Hidden Leaf Village and Akatsuki finding out about Naruto's recent achievement. Plus, I'll be ending it with a cliffhanger.

Now, I have some good news and bad news. That should be expected, shouldn't it? That almost always happens.

The good news: The Shadows of Caldreth is almost finished, and I will be working on finishing the next arcs in my two active fanfics.

The bad news: I am going to be ending Naruto: A New Destiny at Chapter 10 and Secrets at Chapter 12.

To clarify, I'm not abandoning either story. I've decided to end them now and do sequels later. Why? Because I don't think I can do them justice if I do them right now. I don't want either one of them to turn into the next Consequences, which can happen if I stretch myself thin like I was doing before I took a break.

Now that the bad news is out of the way, let me give everyone a heads up on what I'm going to be doing. I'll write one original fiction and one fanfiction at any given time, and the fanfiction I have in mind first will not be one of the sequels. I want to give myself some more time away from them before I do the sequels so I can keep up the quality.

So what will I be doing?

I'll be doing a Naruto crossover fanfic. Yeah, I always said I wouldn't do one, but I changed my mind about that.

The past week or so, I got an interest in Fairy Tail. It has since become my favorite anime/manga, and I've watched the first season of the anime (48 episodes) in the past three days. So I'll be doing a fanfic where Naruto enters the Fairy Tail world within the next week. Naturally, I'm not expecting too many of my current readers to take an interest in it. After all, I have no idea how many of my readers have even watched or read Fairy Tail. Regardless, fanfiction is a hobby of mine, and so I'll do whatever I think will be most fun.


	10. An Unexpected Situation

Disclaimer: I do not own Naruto.

* * *

**Out of the Shadows Arc**

**10. An Unexpected Situation**

"Do you know why I've summoned you?" Tsunade asked as she sat in her chair with her elbows on her desk and her chin resting on her interlocked fingers.

"I think so," Kakashi Hatake said as he looked at her from his chair. Kurenai Yuhi, Asuma Sarutobi, and Might Guy were sitting in the chairs next to him. They all looked far more attentive than normal.

"Today, I received word from the new Kazekage. Sasori of the Red Sand, a rogue ninja from their village and a member of the Akatsuki organization, has been captured. He was defeated by none other than Naruto Uzumaki," Tsunade said.

Whatever her guests had expected, that was not it.

"Has he truly gotten that strong?" Kakashi asked in surprise.

"They captured him alive," Tsunade suddenly said, surprising them all even more.

"Alive," Kakashi said quietly. "That's a feat in itself, but why did you say that _they_ captured him alive? I thought it was Naruto."

"He has an accomplice," Tsunade said with a frown. "I believe that I know who it is, as a matter of fact. Unfortunately, it's just speculation for now. Ever since Jiraiya decided to fully retire, our information network has become somewhat less effective."

"We need to work on capturing him now then," Kurenai suddenly said. "If he's strong enough to defeat Sasori of the Red Sand, it'll be difficult. However, he's starting to draw attention to himself."

"He is not to be captured," Tsunade said with a heavy sigh. "The Feudal Lord would not be forgiving if we outright captured him. No, we will work on finding him and asking him to return to the village. If he attacks anyone that confronts him, it would be appropriate to immobilize him and take him somewhere safe though."

Kakashi frowned at that, and it was pretty easy to see why. Tsunade was just looking to exploit a technically to get Naruto back.

"If Naruto loses control, he could destroy anyone we send after him," Asuma countered.

"That's not what should worry you," Kakashi interjected before Tsunade could say something. "What if he's gained control of the Nine-Tails already? With its power, he could destroy anyone we send after him. Let's face it, he has good reason to hate our village."

"And how is that?" Tsunade asked dangerously.

"If I answer that question, you're going to get very angry," Kakashi said seriously. "I share the same viewpoint of Jiraiya, so don't ask what I mean unless you really want to know."

Tsunade glared at him momentarily, but she soon turned her attention away from him.

"Kurenai Yuhi, I want you to prepare your team. Tomorrow, I want you to work on tracking Naruto down. If anyone can do it, your team can. If you do find him, it would be a good idea to take note of any abilities that he displays, even if you can't get him to come with you. As it is now, we don't know what kind of abilities he has."

"Understood," Kurenai said with a nod. She could not help but have a bad feeling about the situation, for some reason.

"You all are dismissed," Tsunade said.

* * *

"What gives? Why did you summon us? I was just about to perform my ritual?" Hidan asked, clearly irritated.

Their leader, Pain, looked around at all of the shinobi in attendance to their meeting. Itachi Uchiha, Kisame Hoshigaki, Kakuzu, HIdan, Konan, and Zetsu had all come. The news that he had heard was troubling, and the absence of Sasori and Deidara only proved what he had been told.

"Sasori and Deidara have been captured," Pain said, earning everyone's attention, though it was already known by Zetsu."Naruto Uzumaki, accompanied by his female companion and the Toad Sage, fought their team and defeated them. What's more is that it appears that the Nine-Tails is in possession of the Uzumaki clan's fuinjutsu."

"I see," Itachi said with a frown. "It appears that he has become even more dangerous than we expected. Who knows, perhaps he has control of the Nine-Tails as well."

"You should hope that he does not," Pain said sternly. "He is still your responsibility to capture, and there is no way we can make a move on him too soon. Containing him while we capture the others would be very difficult, especially if he has the Toad Sage on his side."

"I understand," Itachi said with a nod of understanding.

"So when shall we make our move?" Kakuzu suddenly asked. "If the Nine-Tails is getting this strong, perhaps we should start making our move now."

"Patience," Pain said calmly. "We still have to capture four tailed beasts before we can capture him. Once we go after the first jinchuriki, we will have to move quickly."

"The Three-Tails does not have a host at this moment," Zetsu suddenly said, earning everyone's attention.

"Very well then," Pain said as he looked at Itachi and Kisame. "Go and capture the Three-Tails right now. In a few months' time, I will send you two to capture the Two-Tails while Kakuzu and Hidan go to capture the One-Tail. Until then, remain in the shadows. You are all dismissed."

One by one, the spectral images of the Akatsuki members disappeared until the only ones left in the cave were Pain and Itachi.

"Madara will not be happy to hear that we've already lost two members," Itachi said. He did not exactly sound displeased by that statement either.

"He won't," Pain agreed. "This is not his Akatsuki anymore though. It is mine. If he wishes to say something about it, then he should have been involved earlier on."

"I understand," Itachi said calmly. "As you are no doubt aware, we are going to have difficult carrying out the captures of the remaining seven tailed beasts at this point. Even if we can capture the One-Tails, Two-Tails, and Three-Tails smoothly, that still lives the Four-Tails, Six-Tails, Eight-Tails, and Nine-Tails. If they get word of what we're planning…."

"I am well aware of the risks," Pain said as he locked eyes with Itachi. "I will have to pitch in if I want our plans to succeed, it seems."

Itachi nodded cautiously and faded from sight.

"He is a suspicious man," Pain said thoughtfully.

* * *

Naruto Uzumaki was sitting in the last place he had ever expected to be: across the desk from the Third Tsuchikage.

It had been relatively awkward walking into the Hidden Rock Village with the unconscious Deidara slung over his shoulder, but the apprentice of the Tsuchikage had a relatively high bounty on his head, so Naruto saw no choice but to bring him in.

Naturally, he had left Tayuya outside of the village. She was not the best person to bring with him for meetings. While he had not been very diplomatic when they met, she was even worse. She had a tendency to cuss anyone out that offended her, which was the opposite of diplomatic.

Still, he did not enjoy being in the village. Naruto was not stupid. He knew why Rock ninja had been looking at him cautiously. He looked very similar to his father, after all.

"So, you actually managed to defeat Deidara," Onoki said as he looked at the unconscious body next to Naruto. "How did you manage it?"

"My team did," Naruto corrected. He had no intention of revealing that it was Jiraiya who defeated Deidara. "He was knocked unconscious, and then I placed a seal on him to completely negate any chakra that he attempted to use. There's a paralysis seal on him too. I couldn't very well let him wake up, of course."

"Of course," Onoki said carefully. "I have to say that you have a lot of nerve coming in here."

"Oh?" Naruto asked curiously.

"I know who you are," Onoki said as he looked at Naruto with a serious look in his eyes. "I can't let the son of the Fourth Hokage just walk away, now can I?"

"You're not going to pay me, are you?" Naruto asked with a sigh that disturbed Onoki. "You should have paid me Deidara's bounty and let me walk out of here. If you change your mind, you won't regret it. If you keep it up, you will though."

"Is that a threat?" Onoki asked as he put his hands together.

"No, it's a promise," Naruto said.

Immediately, Naruto was surrounded by Onoki's dust style ninjutsu.

"Good riddance, Namikaze," Onoki said as he activated the jutsu.

Dust suddenly filled the area where Naruto had been as he was turned completely to dust.

Immediately afterwards, Onoki's eyes went to Deidara's body. There was an unnatural amount of chakra building up, and its source was his body.

At a closer inspection, Onoki recognize writing on Deidara's skin. It was the same writing that was on paper bombs.

_No… this isn't good._

Those were his last thoughts as Deidara's body exploded with the force of a thousand paper bombs.

* * *

Miles away from the village, Naruto punched the wall of the cave he was in.

"Damn it, the old bastard turned on me. It's a good thing I listened to you when you told me to use a shadow clone," he said with annoyance clear in his eyes.

"You had to know that he would want you dead," Tayuya remarked, though it was clear she was annoyed as well. They had good reason to be annoyed. They were out forty million ryo thanks to Onoki's treachery.

"Well, we need to get a move on," Naruto said, shaking his head. "I kind of blew up their administration building. I didn't trust them, so I drew the seals for paper bombs all over his arms and torso when you were sleeping. The trigger for the paper bombs was the violent destruction of my clone."

Tayuya shook her head, exasperated. "Do you have any idea how many people you killed and injured?"

"Yeah," Naruto said with a small laugh. "I guess I have more in common with my dad than I thought."

And so the Son of the Yellow Flash left his mark upon the world.

It was just the beginning though. He still had a great destiny before him.

* * *

Author's Note: Thanks for reading. Naruto: A New Destiny is officially over. I'm not sure what the name of the sequel will be, but that's a matter for a later date.


End file.
